OpenCores
URL https://opencores.org/ocsvn/sudoku/sudoku/trunk

Subversion Repositories sudoku

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /
    from Rev 5 to Rev 6
    ↔ Reverse comparison
  •

Rev 5 → Rev 6

/sudoku/branches/zynq/rtl/user_logic.v
0,0 → 1,128
//----------------------------------------------------------------------------
// user_logic.v - module
//----------------------------------------------------------------------------
//
// ***************************************************************************
// ** Copyright (c) 1995-2012 Xilinx, Inc. All rights reserved. **
// ** **
// ** Xilinx, Inc. **
// ** XILINX IS PROVIDING THIS DESIGN, CODE, OR INFORMATION "AS IS" **
// ** AS A COURTESY TO YOU, SOLELY FOR USE IN DEVELOPING PROGRAMS AND **
// ** SOLUTIONS FOR XILINX DEVICES. BY PROVIDING THIS DESIGN, CODE, **
// ** OR INFORMATION AS ONE POSSIBLE IMPLEMENTATION OF THIS FEATURE, **
// ** APPLICATION OR STANDARD, XILINX IS MAKING NO REPRESENTATION **
// ** THAT THIS IMPLEMENTATION IS FREE FROM ANY CLAIMS OF INFRINGEMENT, **
// ** AND YOU ARE RESPONSIBLE FOR OBTAINING ANY RIGHTS YOU MAY REQUIRE **
// ** FOR YOUR IMPLEMENTATION. XILINX EXPRESSLY DISCLAIMS ANY **
// ** WARRANTY WHATSOEVER WITH RESPECT TO THE ADEQUACY OF THE **
// ** IMPLEMENTATION, INCLUDING BUT NOT LIMITED TO ANY WARRANTIES OR **
// ** REPRESENTATIONS THAT THIS IMPLEMENTATION IS FREE FROM CLAIMS OF **
// ** INFRINGEMENT, IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS **
// ** FOR A PARTICULAR PURPOSE. **
// ** **
// ***************************************************************************
//
//----------------------------------------------------------------------------
// Filename: user_logic.v
// Version: 1.00.a
// Description: User logic module.
// Date: Wed Dec 12 22:58:12 2012 (by Create and Import Peripheral Wizard)
// Verilog Standard: Verilog-2001
//----------------------------------------------------------------------------
// Naming Conventions:
// active low signals: "*_n"
// clock signals: "clk", "clk_div#", "clk_#x"
// reset signals: "rst", "rst_n"
// generics: "C_*"
// user defined types: "*_TYPE"
// state machine next state: "*_ns"
// state machine current state: "*_cs"
// combinatorial signals: "*_com"
// pipelined or register delay signals: "*_d#"
// counter signals: "*cnt*"
// clock enable signals: "*_ce"
// internal version of output port: "*_i"
// device pins: "*_pin"
// ports: "- Names begin with Uppercase"
// processes: "*_PROCESS"
// component instantiations: "<ENTITY_>I_<#|FUNC>"
//----------------------------------------------------------------------------
 
`uselib lib=unisims_ver
`uselib lib=proc_common_v3_00_a
 
module user_logic
(
// -- ADD USER PORTS BELOW THIS LINE ---------------
// --USER ports added here
// -- ADD USER PORTS ABOVE THIS LINE ---------------
 
// -- DO NOT EDIT BELOW THIS LINE ------------------
// -- Bus protocol ports, do not add to or delete
Bus2IP_Clk, // Bus to IP clock
Bus2IP_Resetn, // Bus to IP reset
Bus2IP_Data, // Bus to IP data bus
Bus2IP_BE, // Bus to IP byte enables
Bus2IP_RdCE, // Bus to IP read chip enable
Bus2IP_WrCE, // Bus to IP write chip enable
IP2Bus_Data, // IP to Bus data bus
IP2Bus_RdAck, // IP to Bus read transfer acknowledgement
IP2Bus_WrAck, // IP to Bus write transfer acknowledgement
IP2Bus_Error // IP to Bus error response
// -- DO NOT EDIT ABOVE THIS LINE ------------------
); // user_logic
 
// -- ADD USER PARAMETERS BELOW THIS LINE ------------
// --USER parameters added here
// -- ADD USER PARAMETERS ABOVE THIS LINE ------------
 
// -- DO NOT EDIT BELOW THIS LINE --------------------
// -- Bus protocol parameters, do not add to or delete
parameter C_NUM_REG = 8;
parameter C_SLV_DWIDTH = 32;
// -- DO NOT EDIT ABOVE THIS LINE --------------------
 
// -- ADD USER PORTS BELOW THIS LINE -----------------
// --USER ports added here
// -- ADD USER PORTS ABOVE THIS LINE -----------------
 
// -- DO NOT EDIT BELOW THIS LINE --------------------
// -- Bus protocol ports, do not add to or delete
input Bus2IP_Clk;
input Bus2IP_Resetn;
input [C_SLV_DWIDTH-1 : 0] Bus2IP_Data;
input [C_SLV_DWIDTH/8-1 : 0] Bus2IP_BE;
input [C_NUM_REG-1 : 0] Bus2IP_RdCE;
input [C_NUM_REG-1 : 0] Bus2IP_WrCE;
output [C_SLV_DWIDTH-1 : 0] IP2Bus_Data;
output IP2Bus_RdAck;
output IP2Bus_WrAck;
output IP2Bus_Error;
// -- DO NOT EDIT ABOVE THIS LINE --------------------
 
 
wire write_ready;
wire read_ready;
 
assign IP2Bus_WrAck = write_ready && Bus2IP_WrCE != 0;
assign IP2Bus_RdAck = read_ready && Bus2IP_RdCE != 0;
assign IP2Bus_Error = 0;
 
Slave s
(
.clk(Bus2IP_Clk),
.reset(!Bus2IP_Resetn),
 
.io_write_valid(Bus2IP_WrCE),
.io_write_ready(write_ready),
.io_write_data(Bus2IP_Data),
.io_write_byteEnable(Bus2IP_BE),
 
.io_read_valid(Bus2IP_RdCE),
.io_read_ready(read_ready),
.io_read_data(IP2Bus_Data)
);
 
endmodule
 
`include "Slave.v"
/sudoku/branches/zynq/rtl/wrap_search.v
0,0 → 1,68
module wrap_search(/*AUTOARG*/
// Outputs
dout, done, error,
// Inputs
clk, rst, start, addr, wr, din
);
input clk;
input rst;
input start;
input [6:0] addr;
input wr;
input [8:0] din;
output [8:0] dout;
 
output done;
output error;
 
wire [728:0] outGrid;
wire [728:0] inGrid;
wire [8:0] outGrid2d [80:0];
reg [8:0] ram [127:0];
 
assign dout = ram[addr];
 
genvar ii;
generate
for(ii=0;ii<81;ii=ii+1)
begin: unflatten
assign outGrid2d[ii] = outGrid[(9*(ii+1))-1:9*ii];
assign inGrid[(9*(ii+1)-1):(9*ii)] = ram[ii];
end
endgenerate
 
 
integer i;
always@(posedge clk)
begin
if(wr)
begin
ram[addr] <= din;
end
else if(done|error)
begin
for(i = 0; i < 81; i=i+1)
begin
ram[i] <= outGrid2d[i];
end
end
end
 
sudoku_search solver0
( // Outputs
.outGrid (outGrid[728:0]),
.done (done),
.error (error),
// Inuts
.clk (clk),
.rst (rst),
.start (start),
.inGrid (inGrid[728:0])
);
 
endmodule // wrap_sudoku
/sudoku/branches/zynq/rtl/sudoku_search.v
0,0 → 1,437
module sudoku_search(/*AUTOARG*/
// Outputs
outGrid, done, error,
// Inputs
clk, rst, start, inGrid
);
parameter LG_DEPTH = 6;
localparam DEPTH = 1 << LG_DEPTH;
input clk;
input rst;
input start;
input [728:0] inGrid;
output [728:0] outGrid;
output done;
output error;
 
reg [4:0] r_state, n_state;
reg [31:0] r_stack_pos, t_stack_pos;
reg [31:0] t_stack_addr;
 
reg t_write_stack, t_read_stack;
reg t_clr, t_start;
reg [6:0] r_minIdx, t_minIdx;
reg [8:0] r_cell, t_cell;
wire [3:0] w_ffs;
wire [8:0] w_ffs_mask;
reg [728:0] r_board, n_board;
wire [728:0] w_stack_out;
reg [728:0] t_stack_in;
 
 
wire [728:0] s_outGrid;
wire [8:0] s_outGrid2d[80:0];
wire [728:0] w_nGrid;
reg [8:0] t_outGrid2d[80:0];
 
reg t_done, r_done;
reg t_error, r_error;
assign done = r_done;
assign error = r_error;
genvar i;
 
assign outGrid = s_outGrid;
wire [6:0] w_minIdx, w_unsolvedCells;
wire [3:0] w_minPoss;
wire w_allDone, w_anyChanged, w_anyError, w_timeOut;
 
generate
for(i=0;i<81;i=i+1)
begin: unflatten
assign s_outGrid2d[i] = s_outGrid[(9*(i+1))-1:9*i];
end
endgenerate
 
integer j;
always@(*)
begin
for(j=0;j<81;j=j+1)
begin
t_outGrid2d[j] = s_outGrid2d[j];
end
t_outGrid2d[r_minIdx] = w_ffs_mask;
end
 
generate
for(i=0;i<81;i=i+1)
begin: flatten
assign w_nGrid[(9*(i+1)-1):(9*i)] = t_outGrid2d[i];
end
endgenerate
 
find_first_set ffs0
(
.in(r_cell),
.out(w_ffs),
.out_mask(w_ffs_mask)
);
always@(*)
begin
t_clr = 1'b0;
t_start = 1'b0;
t_write_stack = 1'b0;
t_read_stack = 1'b0;
t_stack_in = 729'd0;
t_stack_pos = r_stack_pos;
t_stack_addr = t_stack_pos;
n_state = r_state;
n_board = r_board;
 
t_minIdx = r_minIdx;
t_cell = r_cell;
 
t_done = r_done;
t_error = r_error;
case(r_state)
/* copy input to stack */
5'd0:
begin
if(start)
begin
t_write_stack = 1'b1;
t_stack_pos = r_stack_pos + 32'd1;
n_state = 5'd1;
t_stack_in = inGrid;
end
else
begin
n_state = 5'd0;
end
end
/* pop state off the top of the stack,
* data valid in the next state */
5'd1:
begin
t_read_stack = 1'b1;
//$display("reading new board");
t_stack_pos = r_stack_pos - 32'd1;
t_stack_addr = t_stack_pos;
n_state = (r_stack_pos == 32'd0) ? 5'd31 : 5'd2;
end
/* data out of stack ram is
* valid .. save in register */
5'd2:
begin
t_clr = 1'b1;
n_board = w_stack_out;
n_state = 5'd3;
end
 
/* stack read..valid in r_state */
5'd3:
begin
t_start = 1'b1;
n_state = 5'd4;
if(r_board === 729'dx)
begin
$display("GOT X!");
$display("%b", r_board);
$finish();
end
end
/* wait for exact cover
* hardware to complete */
5'd4:
begin
if(w_allDone)
begin
n_state = w_anyError ? 5'd1 : 5'd8;
end
else if(w_timeOut)
begin
t_minIdx = w_minIdx;
n_state = 5'd5;
end
else
begin
n_state = 5'd4;
end
end // case: 5'd4
 
5'd5:
begin
/* extra cycle */
t_cell = s_outGrid2d[r_minIdx];
n_state = 5'd6;
end
/* timeOut -> push next states onto the stack */
5'd6:
begin
/* if min cell is zero, the board is incorrect
* and we have no need to push successors */
if(r_cell == 9'd0)
begin
n_state = 5'd1;
end
else
begin
t_cell = r_cell & (~w_ffs_mask);
t_stack_in = w_nGrid;
t_write_stack = 1'b1;
t_stack_pos = r_stack_pos + 32'd1;
n_state = (t_stack_pos == (DEPTH-1)) ? 5'd31: 5'd7;
end
end
 
5'd7:
begin
n_state = (r_cell == 9'd0) ? 5'd1 : 5'd6;
end
 
5'd8:
begin
t_done = 1'b1;
n_state = 5'd8;
end
5'd31:
begin
n_state = 5'd31;
t_error = 1'b1;
end
default:
begin
n_state = 5'd0;
end
endcase // case (r_state)
end
 
always@(posedge clk)
begin
if(rst)
begin
r_board <= 729'd0;
r_state <= 5'd0;
r_stack_pos <= 32'd0;
r_minIdx <= 7'd0;
r_cell <= 9'd0;
r_done <= 1'b0;
r_error <= 1'b0;
end
else
begin
r_board <= n_board;
r_state <= n_state;
r_stack_pos <= t_stack_pos;
r_minIdx <= t_minIdx;
r_cell <= t_cell;
r_done <= t_done;
r_error <= t_error;
end
end // always@ (posedge clk)
 
/* stack ram */
stack_ram #(.LG_DEPTH(LG_DEPTH)) stack0
(
// Outputs
.d_out (w_stack_out),
// Inputs
.clk (clk),
.w (t_write_stack),
.addr (t_stack_addr[(LG_DEPTH-1):0] ),
.d_in (t_stack_in)
);
 
sudoku cover0 (
// Outputs
.outGrid (s_outGrid),
.unsolvedCells (w_unsolvedCells),
.timeOut (w_timeOut),
.allDone (w_allDone),
.anyChanged (w_anyChanged),
.anyError (w_anyError),
.minIdx (w_minIdx),
.minPoss (w_minPoss),
// Inputs
.clk (clk),
.rst (rst),
.clr (t_clr),
.start (t_start),
.inGrid (r_board)
);
endmodule // sudoku_search
 
 
 
module stack_ram(/*AUTOARG*/
// Outputs
d_out,
// Inputs
clk, w, addr, d_in
);
parameter LG_DEPTH = 4;
localparam DEPTH = 1 << LG_DEPTH;
input clk;
input w;
input [(LG_DEPTH-1):0] addr;
input [728:0] d_in;
output [728:0] d_out;
 
reg [728:0] r_dout;
assign d_out = r_dout;
 
reg [728:0] mem [(DEPTH-1):0];
always@(posedge clk)
begin
if(w)
begin
if(d_in == 729'dx)
begin
$display("pushing X!!!");
$finish();
end
mem[addr] <= d_in;
end
else
begin
r_dout <= mem[addr];
end
end // always@ (posedge clk)
 
endmodule // stack_ram
 
module find_first_set(out,out_mask,in);
input [8:0] in;
output [3:0] out;
output [8:0] out_mask;
genvar i;
wire [8:0] w_fz;
wire [8:0] w_fzo;
assign w_fz[0] = in[0];
assign w_fzo[0] = in[0];
 
assign out = (w_fzo == 9'd1) ? 4'd1 :
(w_fzo == 9'd2) ? 4'd2 :
(w_fzo == 9'd4) ? 4'd3 :
(w_fzo == 9'd8) ? 4'd4 :
(w_fzo == 9'd16) ? 4'd5 :
(w_fzo == 9'd32) ? 4'd6 :
(w_fzo == 9'd64) ? 4'd7 :
(w_fzo == 9'd128) ? 4'd8 :
(w_fzo == 9'd256) ? 4'd9 :
4'hf;
 
assign out_mask = w_fzo;
generate
for(i=1;i<9;i=i+1)
begin : www
fz fzN (
.out(w_fzo[i]),
.f_out(w_fz[i]),
.f_in(w_fz[i-1]),
.in(in[i])
);
end
endgenerate
endmodule // find_first_set
 
module fz(/*AUTOARG*/
// Outputs
out, f_out,
// Inputs
f_in, in
);
input f_in;
input in;
output out;
output f_out;
assign out = in & (~f_in);
assign f_out = f_in | in;
endmodule
 
 
module checkCorrect(/*AUTOARG*/
// Outputs
y,
// Inputs
in
);
input [80:0] in;
output y;
wire [8:0] grid1d [8:0];
wire [8:0] w_set;
wire [8:0] w_gridOR =
grid1d[0] |
grid1d[1] |
grid1d[2] |
grid1d[3] |
grid1d[4] |
grid1d[5] |
grid1d[6] |
grid1d[7] |
grid1d[8];
wire w_allSet = (w_gridOR == 9'b111111111);
wire w_allAssign = (w_set == 9'b111111111);
assign y = w_allSet & w_allAssign;
 
genvar i;
generate
for(i=0;i<9;i=i+1)
begin: unflatten
assign grid1d[i] = in[(9*(i+1))-1:9*i];
assign w_set[i] =
(grid1d[i] == 9'd1) |
(grid1d[i] == 9'd2) |
(grid1d[i] == 9'd4) |
(grid1d[i] == 9'd8) |
(grid1d[i] == 9'd16) |
(grid1d[i] == 9'd32) |
(grid1d[i] == 9'd64) |
(grid1d[i] == 9'd128) |
(grid1d[i] == 9'd256);
end
endgenerate
endmodule // correct
/sudoku/branches/zynq/rtl/piece.v
0,0 → 1,325
module piece(/*AUTOARG*/
// Outputs
changed, done, curr_value, error,
// Inputs
clk, rst, start, clr, start_value, my_row, my_col, my_square
);
input clk;
input rst;
input start;
input clr;
output changed;
output done;
output error;
input [8:0] start_value;
output [8:0] curr_value;
input [71:0] my_row;
input [71:0] my_col;
input [71:0] my_square;
wire [8:0] row2d [7:0];
wire [8:0] col2d [7:0];
wire [8:0] sqr2d [7:0];
 
wire [8:0] row2d_solv [7:0];
wire [8:0] col2d_solv [7:0];
wire [8:0] sqr2d_solv [7:0];
 
reg [8:0] r_curr_value;
reg [8:0] t_next_value;
assign curr_value = r_curr_value;
 
reg [2:0] r_state, n_state;
reg r_solved, t_solved;
reg t_changed,r_changed;
reg t_error,r_error;
assign done = r_solved;
assign changed = r_changed;
assign error = r_error;
wire [8:0] w_solved;
wire w_piece_solved = (w_solved != 9'd0);
one_set s0 (r_curr_value, w_solved);
always@(posedge clk)
begin
if(rst)
begin
r_curr_value <= 9'd0;
r_state <= 3'd0;
r_solved <= 1'b0;
r_changed <= 1'b0;
r_error <= 1'b0;
end
else
begin
r_curr_value <= clr ? 9'd0 : t_next_value;
r_state <= clr ? 3'd0 : n_state;
r_solved <= clr ? 1'b0 : t_solved;
r_changed <= clr ? 1'b0 : t_changed;
r_error <= clr ? 1'b0 : t_error;
end
end // always@ (posedge clk)
 
genvar i;
generate
for(i=0;i<8;i=i+1)
begin: unflatten
assign row2d[i] = my_row[(9*(i+1))-1:9*i];
assign col2d[i] = my_col[(9*(i+1))-1:9*i];
assign sqr2d[i] = my_square[(9*(i+1))-1:9*i];
end
endgenerate
 
generate
for(i=0;i<8;i=i+1)
begin: unique_rows
one_set rs (row2d[i], row2d_solv[i]);
one_set cs (col2d[i], col2d_solv[i]);
one_set ss (sqr2d[i], sqr2d_solv[i]);
end
endgenerate
 
/* OR output of one_set to find cells
* that are already set in col, grid, row */
 
wire [8:0] set_row =
row2d_solv[0] | row2d_solv[1] | row2d_solv[2] |
row2d_solv[3] | row2d_solv[4] | row2d_solv[5] |
row2d_solv[6] | row2d_solv[7];
wire [8:0] set_col =
col2d_solv[0] | col2d_solv[1] | col2d_solv[2] |
col2d_solv[3] | col2d_solv[4] | col2d_solv[5] |
col2d_solv[6] | col2d_solv[7];
wire [8:0] set_sqr =
sqr2d_solv[0] | sqr2d_solv[1] | sqr2d_solv[2] |
sqr2d_solv[3] | sqr2d_solv[4] | sqr2d_solv[5] |
sqr2d_solv[6] | sqr2d_solv[7];
 
integer ii;
always@(posedge clk)
begin
if(rst==1'b0)
begin
for(ii=0;ii<8;ii=ii+1)
begin
if(row2d_solv[ii] === 9'dx)
begin
$display("row %d", ii);
$stop();
end
end
end
//$display("row2d_solv[0] = %x", row2d_solv[0]);
end
 
 
/* finding unique */
wire [8:0] row_or =
row2d[0] | row2d[1] | row2d[2] |
row2d[3] | row2d[4] | row2d[5] |
row2d[6] | row2d[7] ;
 
wire [8:0] col_or =
col2d[0] | col2d[1] | col2d[2] |
col2d[3] | col2d[4] | col2d[5] |
col2d[6] | col2d[7] ;
wire [8:0] sqr_or =
sqr2d[0] | sqr2d[1] | sqr2d[2] |
sqr2d[3] | sqr2d[4] | sqr2d[5] |
sqr2d[6] | sqr2d[7] ;
 
 
wire [8:0] row_nor = ~row_or;
wire [8:0] col_nor = ~col_or;
wire [8:0] sqr_nor = ~sqr_or;
 
wire [8:0] row_singleton;
wire [8:0] col_singleton;
wire [8:0] sqr_singleton;
one_set s1 (r_curr_value & row_nor, row_singleton);
one_set s2 (r_curr_value & col_nor, col_singleton);
one_set s3 (r_curr_value & sqr_nor, sqr_singleton);
/* these are the values of the set rows, columns, and
* squares */
wire [8:0] not_poss = set_row | set_col | set_sqr;
wire [8:0] new_poss = r_curr_value & (~not_poss);
wire w_piece_zero = (r_curr_value == 9'd0);
always@(*)
begin
t_next_value = r_curr_value;
n_state = r_state;
t_solved = r_solved;
t_changed = 1'b0;
t_error = r_error;
case(r_state)
3'd0:
begin
if(start)
begin
t_next_value = start_value;
n_state = 3'd1;
t_changed = 1'b1;
t_error = 1'b0;
end
end
3'd1:
begin
if(w_piece_solved | w_piece_zero)
begin
t_solved = 1'b1;
n_state = 3'd7;
t_changed = 1'b1;
t_error = w_piece_zero;
end
else
begin
t_changed = (new_poss != r_curr_value);
t_next_value = new_poss;
n_state = 3'd2;
end
end // case: 3'd1
3'd2:
begin
if(w_piece_solved | w_piece_zero)
begin
t_solved = 1'b1;
n_state = 3'd7;
t_error = w_piece_zero;
end
else
begin
if(row_singleton != 9'd0)
begin
//$display("used row singleton");
t_next_value = row_singleton;
t_changed = 1'b1;
t_solved = 1'b1;
n_state = 3'd7;
end
else if(col_singleton != 9'd0)
begin
//$display("used col singleton");
t_next_value = col_singleton;
t_changed = 1'b1;
t_solved = 1'b1;
n_state = 3'd7;
end
else if(sqr_singleton != 9'd0)
begin
//$display("used sqr singleton");
t_next_value = sqr_singleton;
t_changed = 1'b1;
t_solved = 1'b1;
n_state = 3'd7;
end
else
begin
n_state = 3'd1;
end
end
end
3'd7:
begin
t_solved = 1'b1;
n_state = 3'd7;
end
 
endcase // case (r_state)
end
endmodule // piece
 
module one_set(input [8:0] in, output [8:0] out);
wire is_pow2 =
(in == 9'd1) | (in == 9'd2) | (in == 9'd4) |
(in == 9'd8) | (in == 9'd16) | (in == 9'd32) |
(in == 9'd64) | (in == 9'd128) | (in == 9'd256);
assign out = {9{is_pow2}} & in;
endmodule // one_set
 
module two_set(input [8:0] in, output [8:0] out);
wire [3:0] c;
one_count9 oc (.in(in), .out(c));
assign out = (c==4'd2) ? in : 9'd0;
endmodule
 
module ones_count81(input [80:0] in, output [6:0] out);
wire [83:0] w_in = {3'd0, in};
wire [2:0] ps [20:0];
 
integer x;
reg [6:0] t_sum;
genvar i;
generate
for(i=0;i<21;i=i+1)
begin : builders
one_count4 os (w_in[(4*(i+1)) - 1 : 4*i], ps[i]);
end
endgenerate
always@(*)
begin
t_sum = 7'd0;
for(x = 0; x < 21; x=x+1)
begin
t_sum = t_sum + {3'd0, ps[x]};
end
end
assign out = t_sum;
endmodule // ones_count81
 
module one_count4(input [3:0] in, output [2:0] out);
assign out =
(in == 4'b0000) ? 3'd0 :
(in == 4'b0001) ? 3'd1 :
(in == 4'b0010) ? 3'd1 :
(in == 4'b0011) ? 3'd2 :
(in == 4'b0100) ? 3'd1 :
(in == 4'b0101) ? 3'd2 :
(in == 4'b0110) ? 3'd2 :
(in == 4'b0111) ? 3'd3 :
(in == 4'b1000) ? 3'd1 :
(in == 4'b1001) ? 3'd2 :
(in == 4'b1010) ? 3'd2 :
(in == 4'b1011) ? 3'd3 :
(in == 4'b1100) ? 3'd2 :
(in == 4'b1101) ? 3'd3 :
(in == 4'b1110) ? 3'd3 :
3'd4;
endmodule // one_count4
 
module one_count9(input [8:0] in, output [3:0] out);
wire [2:0] o0, o1;
one_count4 m0 (in[3:0], o0);
one_count4 m1 (in[7:4], o1);
 
assign out = {3'd0,in[8]} + {1'd0,o1} + {1'd0,o0};
 
endmodule
/sudoku/branches/zynq/rtl/minPiece.v
0,0 → 1,284
`define PIPE_MINPIECE 1
 
module minPiece(/*AUTOARG*/
// Outputs
minPoss, minIdx,
// Inputs
clk, rst, inGrid
);
 
input clk;
input rst;
input [728:0] inGrid;
output [3:0] minPoss;
output [6:0] minIdx;
reg [3:0] r_minPoss;
reg [6:0] r_minIdx;
 
assign minPoss = r_minPoss;
assign minIdx = r_minIdx;
wire [8:0] grid2d [80:0];
 
wire [6:0] gridIndices [80:0];
wire [3:0] gridPoss [80:0];
genvar i;
 
/* unflatten */
generate
for(i=0;i<81;i=i+1)
begin: unflatten
assign grid2d[i] = inGrid[(9*(i+1))-1:9*i];
assign gridIndices[i] = i;
countPoss cP (.clk(clk), .rst(rst), .in(grid2d[i]), .out(gridPoss[i]));
end
endgenerate
 
wire [6:0] stage1_gridIndices [39:0];
wire [3:0] stage1_gridPoss [39:0];
 
generate
for(i=0;i<40;i=i+1)
begin: stage1
cmpPiece cP_stage1
(
.outPoss(stage1_gridPoss[i]),
.outIdx(stage1_gridIndices[i]),
.inPoss_0(gridPoss[2*i]),
.inIdx_0(gridIndices[2*i]),
.inPoss_1(gridPoss[2*i+1]),
.inIdx_1(gridIndices[2*i+1])
);
end
endgenerate
 
wire [6:0] stage2_gridIndices [19:0];
wire [3:0] stage2_gridPoss [19:0];
 
generate
for(i=0;i<20;i=i+1)
begin: stage2
cmpPiece cP_stage2
(
.outPoss(stage2_gridPoss[i]),
.outIdx(stage2_gridIndices[i]),
.inPoss_0(stage1_gridPoss[2*i]),
.inIdx_0(stage1_gridIndices[2*i]),
.inPoss_1(stage1_gridPoss[2*i+1]),
.inIdx_1(stage1_gridIndices[2*i+1])
);
end
endgenerate
 
wire [6:0] stage3_gridIndices [9:0];
wire [3:0] stage3_gridPoss [9:0];
 
`ifdef PIPE_MINPIECE
wire [6:0] r_stage3_gridIndices [9:0];
wire [3:0] r_stage3_gridPoss [9:0];
wire [6:0] r_gridIndices_80;
wire [3:0] r_gridPoss_80;
dff#(.WIDTH(4)) r_poss80
(.clk(clk),
.rst(rst),
.d(gridPoss[80]),
.q(r_gridPoss_80)
);
dff#(.WIDTH(7)) r_index80
(.clk(clk),
.rst(rst),
.d(gridIndices[80]),
.q(r_gridIndices_80)
);
generate
for(i=0;i<10;i=i+1)
begin: pipelatch
dff#(.WIDTH(7)) rT_index3
(.clk(clk),
.rst(rst),
.d(stage3_gridIndices[i]),
.q(r_stage3_gridIndices[i])
);
dff#(.WIDTH(4)) rT_poss3
(.clk(clk),
.rst(rst),
.d(stage3_gridPoss[i]),
.q(r_stage3_gridPoss[i])
);
 
end // block: pipelatch
endgenerate
`endif
generate
for(i=0;i<10;i=i+1)
begin: stage3
cmpPiece cP_stage3
(
.outPoss(stage3_gridPoss[i]),
.outIdx(stage3_gridIndices[i]),
.inPoss_0(stage2_gridPoss[2*i]),
.inIdx_0(stage2_gridIndices[2*i]),
.inPoss_1(stage2_gridPoss[2*i+1]),
.inIdx_1(stage2_gridIndices[2*i+1])
);
end
endgenerate
 
wire [6:0] stage4_gridIndices [4:0];
wire [3:0] stage4_gridPoss [4:0];
 
generate
for(i=0;i<5;i=i+1)
begin: stage4
cmpPiece cP_stage4
(
.outPoss(stage4_gridPoss[i]),
.outIdx(stage4_gridIndices[i]),
`ifdef PIPE_MINPIECE
.inPoss_0(r_stage3_gridPoss[2*i]),
.inIdx_0(r_stage3_gridIndices[2*i]),
.inPoss_1(r_stage3_gridPoss[2*i+1]),
.inIdx_1(r_stage3_gridIndices[2*i+1])
`else
.inPoss_0(stage3_gridPoss[2*i]),
.inIdx_0(stage3_gridIndices[2*i]),
.inPoss_1(stage3_gridPoss[2*i+1]),
.inIdx_1(stage3_gridIndices[2*i+1])
`endif
);
end
endgenerate
 
wire [6:0] stage5_gridIndices [1:0];
wire [3:0] stage5_gridPoss [1:0];
 
generate
for(i=0;i<2;i=i+1)
begin: stage5
cmpPiece cP_stage5
(
.outPoss(stage5_gridPoss[i]),
.outIdx(stage5_gridIndices[i]),
.inPoss_0(stage4_gridPoss[2*i]),
.inIdx_0(stage4_gridIndices[2*i]),
.inPoss_1(stage4_gridPoss[2*i+1]),
.inIdx_1(stage4_gridIndices[2*i+1])
);
end
endgenerate
 
 
wire [6:0] stage6_gridIndices_A;
wire [3:0] stage6_gridPoss_A;
 
cmpPiece cP_stage6_A
(
.outPoss(stage6_gridPoss_A),
.outIdx(stage6_gridIndices_A),
.inPoss_0(stage5_gridPoss[0]),
.inIdx_0(stage5_gridIndices[0]),
.inPoss_1(stage5_gridPoss[1]),
.inIdx_1(stage5_gridIndices[1])
);
wire [6:0] stage6_gridIndices_B;
wire [3:0] stage6_gridPoss_B;
cmpPiece cP_stage6_B
(
.outPoss(stage6_gridPoss_B),
.outIdx(stage6_gridIndices_B),
.inPoss_0(stage4_gridPoss[4]),
.inIdx_0(stage4_gridIndices[4]),
`ifdef PIPE_MINPIECE
.inPoss_1(r_gridPoss_80),
.inIdx_1(r_gridIndices_80)
`else
.inPoss_1(gridPoss[80]),
.inIdx_1(gridIndices[80])
`endif
);
wire [6:0] stage7_gridIndices;
wire [3:0] stage7_gridPoss;
cmpPiece cP_stage7
(
.outPoss(stage7_gridPoss),
.outIdx(stage7_gridIndices),
.inPoss_0(stage6_gridPoss_A),
.inIdx_0(stage6_gridIndices_A),
.inPoss_1(stage6_gridPoss_B),
.inIdx_1(stage6_gridIndices_B)
);
 
always@(posedge clk)
begin
if(rst)
begin
r_minIdx <= 7'd0;
r_minPoss <= 4'hf;
end
else
begin
r_minIdx <= stage7_gridIndices;
r_minPoss <= stage7_gridPoss;
end
end // always@ (posedge clk)
endmodule
 
module cmpPiece(/*AUTOARG*/
// Outputs
outPoss, outIdx,
// Inputs
inPoss_0, inIdx_0, inPoss_1, inIdx_1
);
input [3:0] inPoss_0;
input [6:0] inIdx_0;
 
input [3:0] inPoss_1;
input [6:0] inIdx_1;
 
output [3:0] outPoss;
output [6:0] outIdx;
 
wire w_cmp = (inPoss_0 < inPoss_1);
 
assign outPoss = w_cmp ? inPoss_0 : inPoss_1;
assign outIdx = w_cmp ? inIdx_0 : inIdx_1;
endmodule // cmpPiece
 
module countPoss(clk,rst,in,out);
input [8:0] in;
input clk;
input rst;
output [3:0] out;
reg [3:0] r_out;
assign out = r_out;
wire [3:0] w_cnt;
one_count9 c0(in, w_cnt);
wire [3:0] w_out = (w_cnt == 4'd1) ? 4'd15 : w_cnt;
 
always@(posedge clk)
begin
r_out <= rst ? 4'd15 : w_out;
end
endmodule
/sudoku/branches/zynq/rtl/Slave.v
0,0 → 1,112
`include "piece.v"
`include "sudoku.v"
`include "sudoku_search.v"
`include "wrap_search.v"
`include "minPiece.v"
 
 
module Slave(input clk,
input reset,
input [7:0] io_write_valid,
output io_write_ready,
input [3:0] io_write_byteEnable,
input [31:0] io_write_data,
input [7:0] io_read_valid,
output io_read_ready,
output [31:0] io_read_data);
 
/* DBS verilog notes:
* rst -> active high reset...
* io_write_valid -> one hot code for write
* io_read_valid -> one hot code for read
*/
reg [31:0] rf[7:0];
 
wire w_read = |io_read_valid;
wire w_write = |io_write_valid;
assign io_read_ready = |io_read_valid;
assign io_write_ready = |io_write_valid;
wire [2:0] r_addr;
wire [2:0] w_addr;
assign r_addr = io_read_valid == 8'd1 ? 3'd0 :
io_read_valid == 8'd2 ? 3'd1 :
io_read_valid == 8'd4 ? 3'd2 :
io_read_valid == 8'd8 ? 3'd3 :
io_read_valid == 8'd16 ? 3'd4 :
io_read_valid == 8'd32 ? 3'd5 :
io_read_valid == 8'd64 ? 3'd6 :
3'd7;
 
assign w_addr = io_write_valid == 8'd1 ? 3'd0 :
io_write_valid == 8'd2 ? 3'd1 :
io_write_valid == 8'd4 ? 3'd2 :
io_write_valid == 8'd8 ? 3'd3 :
io_write_valid == 8'd16 ? 3'd4 :
io_write_valid == 8'd32 ? 3'd5 :
io_write_valid == 8'd64 ? 3'd6 :
3'd7;
assign io_read_data = w_read ? rf[r_addr] : 32'hffffffff;
 
wire [8:0] w_dout;
wire w_start;
 
assign w_start = rf[7][0];
 
wire w_wr;
wire [6:0] w_saddr;
wire [8:0] w_din;
assign w_wr = rf[1][31];
assign w_saddr = rf[1][6:0];
assign w_din = rf[1][15:7];
wire w_done, w_error;
always@(posedge clk)
begin
if(reset)
begin
rf[0] <= 32'd0;
rf[1] <= 32'd0;
rf[2] <= 32'd0;
rf[3] <= 32'd0;
rf[7] <= 32'd0;
end
else
begin
rf[0] <= {32'd0, w_error, w_done};
/* fire for one cycle */
rf[7] <= (w_write && (w_addr == 3'd7)) ? io_write_data : 32'd0;
 
if(w_write && (w_addr == 3'd1))
begin
rf[1] <= io_write_data;
end
rf[2] <= {23'd0, w_dout};
end
end
wrap_search solver0 (
// Outputs
.dout (w_dout),
.done (w_done),
.error (w_error),
// Inputs
.clk (clk),
.rst (reset),
.start (w_start),
.addr (w_saddr),
.wr (w_wr),
.din (w_din)
);
 
 
endmodule
 
/sudoku/branches/zynq/rtl/sudoku.v
0,0 → 1,506
module dff(clk,rst,d,q);
input clk;
input rst;
parameter WIDTH = 10;
input [(WIDTH-1):0] d;
output [(WIDTH-1):0] q;
reg [(WIDTH-1):0] r_q;
assign q = r_q;
always@(posedge clk)
begin
if(rst)
begin
r_q <= 'd0;
end
else
begin
r_q <= d;
end
end
endmodule // dff
 
module sudoku(/*AUTOARG*/
// Outputs
outGrid, unsolvedCells, timeOut, allDone, anyChanged, anyError,
minIdx, minPoss,
// Inputs
clk, rst, clr, start, inGrid
);
input clk;
input rst;
input clr;
input start;
input [728:0] inGrid;
output [728:0] outGrid;
output [6:0] unsolvedCells;
output timeOut;
output allDone;
output anyChanged;
output anyError;
 
output [6:0] minIdx;
output [3:0] minPoss;
wire [8:0] grid2d [80:0];
wire [8:0] currGrid [80:0];
wire [80:0] done;
wire [80:0] changed;
wire [80:0] error;
wire [71:0] rows [80:0];
wire [71:0] cols [80:0];
wire [71:0] sqrs [80:0];
 
wire [71:0] r_rows [80:0];
wire [71:0] r_cols [80:0];
wire [71:0] r_sqrs [80:0];
 
//assign allDone = &done;
//assign anyChanged = |changed;
reg r_done, r_changed, r_error;
assign allDone = r_done;
assign anyChanged = r_changed;
assign anyError = r_error;
reg [3:0] r_cnt;
assign timeOut = (r_cnt == 4'b0100);
always@(posedge clk)
begin
if(rst)
begin
r_cnt <= 4'd0;
end
else
begin
r_cnt <= start ? 4'd0 : (r_changed ? 4'd0 : r_cnt + 4'd1);
end
end // always@ (posedge clk)
 
minPiece mP0
(
.minPoss(minPoss),
.minIdx(minIdx),
.clk(clk),
.rst(rst),
.inGrid(outGrid)
);
genvar i;
generate
for(i=0;i<81;i=i+1)
begin: unflatten
assign grid2d[i] = inGrid[(9*(i+1))-1:9*i];
end
endgenerate
 
generate
for(i=0;i<81;i=i+1)
begin: pipeline_wires
dff#(.WIDTH(72)) pipe_rows
(.clk(clk),
.rst(rst),
.d(rows[i]),
.q(r_rows[i])
);
dff#(.WIDTH(72)) pipe_cols
(.clk(clk),
.rst(rst),
.d(cols[i]),
.q(r_cols[i])
);
dff#(.WIDTH(72)) pipe_sqrs
(.clk(clk),
.rst(rst),
.d(sqrs[i]),
.q(r_sqrs[i])
);
end
endgenerate
wire [6:0] w_unSolvedCells;
reg [6:0] r_unSolvedCells;
always@(posedge clk)
begin
if(rst)
begin
r_unSolvedCells <= 7'd81;
end
else
begin
r_unSolvedCells <= start ? 7'd81 : w_unSolvedCells;
end
end // always@ (posedge clk)
assign unsolvedCells = r_unSolvedCells;
ones_count81 oc0 (.in(~done), .out(w_unSolvedCells));
generate
for(i=0;i<81;i=i+1)
begin: pieces
piece pg (
// Outputs
.changed (changed[i]),
.done (done[i]),
.curr_value (currGrid[i]),
.error (error[i]),
// Inputs
.clk (clk),
.rst (rst),
.clr (clr),
.start (start),
.start_value (grid2d[i]),
.my_row (r_rows[i]),
.my_col (r_cols[i]),
.my_square (r_sqrs[i])
);
end // block: pieces
endgenerate
assign cols[0] = {currGrid[9],currGrid[18],currGrid[27],currGrid[36],currGrid[45],currGrid[54],currGrid[63],currGrid[72]};
assign rows[0] = {currGrid[1],currGrid[2],currGrid[3],currGrid[4],currGrid[5],currGrid[6],currGrid[7],currGrid[8]};
assign sqrs[0] = {currGrid[1],currGrid[2],currGrid[9],currGrid[10],currGrid[11],currGrid[18],currGrid[19],currGrid[20]};
assign cols[1] = {currGrid[10],currGrid[19],currGrid[28],currGrid[37],currGrid[46],currGrid[55],currGrid[64],currGrid[73]};
assign rows[1] = {currGrid[0],currGrid[2],currGrid[3],currGrid[4],currGrid[5],currGrid[6],currGrid[7],currGrid[8]};
assign sqrs[1] = {currGrid[0],currGrid[2],currGrid[9],currGrid[10],currGrid[11],currGrid[18],currGrid[19],currGrid[20]};
assign cols[2] = {currGrid[11],currGrid[20],currGrid[29],currGrid[38],currGrid[47],currGrid[56],currGrid[65],currGrid[74]};
assign rows[2] = {currGrid[0],currGrid[1],currGrid[3],currGrid[4],currGrid[5],currGrid[6],currGrid[7],currGrid[8]};
assign sqrs[2] = {currGrid[0],currGrid[1],currGrid[9],currGrid[10],currGrid[11],currGrid[18],currGrid[19],currGrid[20]};
assign cols[3] = {currGrid[12],currGrid[21],currGrid[30],currGrid[39],currGrid[48],currGrid[57],currGrid[66],currGrid[75]};
assign rows[3] = {currGrid[0],currGrid[1],currGrid[2],currGrid[4],currGrid[5],currGrid[6],currGrid[7],currGrid[8]};
assign sqrs[3] = {currGrid[4],currGrid[5],currGrid[12],currGrid[13],currGrid[14],currGrid[21],currGrid[22],currGrid[23]};
assign cols[4] = {currGrid[13],currGrid[22],currGrid[31],currGrid[40],currGrid[49],currGrid[58],currGrid[67],currGrid[76]};
assign rows[4] = {currGrid[0],currGrid[1],currGrid[2],currGrid[3],currGrid[5],currGrid[6],currGrid[7],currGrid[8]};
assign sqrs[4] = {currGrid[3],currGrid[5],currGrid[12],currGrid[13],currGrid[14],currGrid[21],currGrid[22],currGrid[23]};
assign cols[5] = {currGrid[14],currGrid[23],currGrid[32],currGrid[41],currGrid[50],currGrid[59],currGrid[68],currGrid[77]};
assign rows[5] = {currGrid[0],currGrid[1],currGrid[2],currGrid[3],currGrid[4],currGrid[6],currGrid[7],currGrid[8]};
assign sqrs[5] = {currGrid[3],currGrid[4],currGrid[12],currGrid[13],currGrid[14],currGrid[21],currGrid[22],currGrid[23]};
assign cols[6] = {currGrid[15],currGrid[24],currGrid[33],currGrid[42],currGrid[51],currGrid[60],currGrid[69],currGrid[78]};
assign rows[6] = {currGrid[0],currGrid[1],currGrid[2],currGrid[3],currGrid[4],currGrid[5],currGrid[7],currGrid[8]};
assign sqrs[6] = {currGrid[7],currGrid[8],currGrid[15],currGrid[16],currGrid[17],currGrid[24],currGrid[25],currGrid[26]};
assign cols[7] = {currGrid[16],currGrid[25],currGrid[34],currGrid[43],currGrid[52],currGrid[61],currGrid[70],currGrid[79]};
assign rows[7] = {currGrid[0],currGrid[1],currGrid[2],currGrid[3],currGrid[4],currGrid[5],currGrid[6],currGrid[8]};
assign sqrs[7] = {currGrid[6],currGrid[8],currGrid[15],currGrid[16],currGrid[17],currGrid[24],currGrid[25],currGrid[26]};
assign cols[8] = {currGrid[17],currGrid[26],currGrid[35],currGrid[44],currGrid[53],currGrid[62],currGrid[71],currGrid[80]};
assign rows[8] = {currGrid[0],currGrid[1],currGrid[2],currGrid[3],currGrid[4],currGrid[5],currGrid[6],currGrid[7]};
assign sqrs[8] = {currGrid[6],currGrid[7],currGrid[15],currGrid[16],currGrid[17],currGrid[24],currGrid[25],currGrid[26]};
assign cols[9] = {currGrid[0],currGrid[18],currGrid[27],currGrid[36],currGrid[45],currGrid[54],currGrid[63],currGrid[72]};
assign rows[9] = {currGrid[10],currGrid[11],currGrid[12],currGrid[13],currGrid[14],currGrid[15],currGrid[16],currGrid[17]};
assign sqrs[9] = {currGrid[0],currGrid[1],currGrid[2],currGrid[10],currGrid[11],currGrid[18],currGrid[19],currGrid[20]};
assign cols[10] = {currGrid[1],currGrid[19],currGrid[28],currGrid[37],currGrid[46],currGrid[55],currGrid[64],currGrid[73]};
assign rows[10] = {currGrid[9],currGrid[11],currGrid[12],currGrid[13],currGrid[14],currGrid[15],currGrid[16],currGrid[17]};
assign sqrs[10] = {currGrid[0],currGrid[1],currGrid[2],currGrid[9],currGrid[11],currGrid[18],currGrid[19],currGrid[20]};
assign cols[11] = {currGrid[2],currGrid[20],currGrid[29],currGrid[38],currGrid[47],currGrid[56],currGrid[65],currGrid[74]};
assign rows[11] = {currGrid[9],currGrid[10],currGrid[12],currGrid[13],currGrid[14],currGrid[15],currGrid[16],currGrid[17]};
assign sqrs[11] = {currGrid[0],currGrid[1],currGrid[2],currGrid[9],currGrid[10],currGrid[18],currGrid[19],currGrid[20]};
assign cols[12] = {currGrid[3],currGrid[21],currGrid[30],currGrid[39],currGrid[48],currGrid[57],currGrid[66],currGrid[75]};
assign rows[12] = {currGrid[9],currGrid[10],currGrid[11],currGrid[13],currGrid[14],currGrid[15],currGrid[16],currGrid[17]};
assign sqrs[12] = {currGrid[3],currGrid[4],currGrid[5],currGrid[13],currGrid[14],currGrid[21],currGrid[22],currGrid[23]};
assign cols[13] = {currGrid[4],currGrid[22],currGrid[31],currGrid[40],currGrid[49],currGrid[58],currGrid[67],currGrid[76]};
assign rows[13] = {currGrid[9],currGrid[10],currGrid[11],currGrid[12],currGrid[14],currGrid[15],currGrid[16],currGrid[17]};
assign sqrs[13] = {currGrid[3],currGrid[4],currGrid[5],currGrid[12],currGrid[14],currGrid[21],currGrid[22],currGrid[23]};
assign cols[14] = {currGrid[5],currGrid[23],currGrid[32],currGrid[41],currGrid[50],currGrid[59],currGrid[68],currGrid[77]};
assign rows[14] = {currGrid[9],currGrid[10],currGrid[11],currGrid[12],currGrid[13],currGrid[15],currGrid[16],currGrid[17]};
assign sqrs[14] = {currGrid[3],currGrid[4],currGrid[5],currGrid[12],currGrid[13],currGrid[21],currGrid[22],currGrid[23]};
assign cols[15] = {currGrid[6],currGrid[24],currGrid[33],currGrid[42],currGrid[51],currGrid[60],currGrid[69],currGrid[78]};
assign rows[15] = {currGrid[9],currGrid[10],currGrid[11],currGrid[12],currGrid[13],currGrid[14],currGrid[16],currGrid[17]};
assign sqrs[15] = {currGrid[6],currGrid[7],currGrid[8],currGrid[16],currGrid[17],currGrid[24],currGrid[25],currGrid[26]};
assign cols[16] = {currGrid[7],currGrid[25],currGrid[34],currGrid[43],currGrid[52],currGrid[61],currGrid[70],currGrid[79]};
assign rows[16] = {currGrid[9],currGrid[10],currGrid[11],currGrid[12],currGrid[13],currGrid[14],currGrid[15],currGrid[17]};
assign sqrs[16] = {currGrid[6],currGrid[7],currGrid[8],currGrid[15],currGrid[17],currGrid[24],currGrid[25],currGrid[26]};
assign cols[17] = {currGrid[8],currGrid[26],currGrid[35],currGrid[44],currGrid[53],currGrid[62],currGrid[71],currGrid[80]};
assign rows[17] = {currGrid[9],currGrid[10],currGrid[11],currGrid[12],currGrid[13],currGrid[14],currGrid[15],currGrid[16]};
assign sqrs[17] = {currGrid[6],currGrid[7],currGrid[8],currGrid[15],currGrid[16],currGrid[24],currGrid[25],currGrid[26]};
assign cols[18] = {currGrid[0],currGrid[9],currGrid[27],currGrid[36],currGrid[45],currGrid[54],currGrid[63],currGrid[72]};
assign rows[18] = {currGrid[19],currGrid[20],currGrid[21],currGrid[22],currGrid[23],currGrid[24],currGrid[25],currGrid[26]};
assign sqrs[18] = {currGrid[0],currGrid[1],currGrid[2],currGrid[9],currGrid[10],currGrid[11],currGrid[19],currGrid[20]};
assign cols[19] = {currGrid[1],currGrid[10],currGrid[28],currGrid[37],currGrid[46],currGrid[55],currGrid[64],currGrid[73]};
assign rows[19] = {currGrid[18],currGrid[20],currGrid[21],currGrid[22],currGrid[23],currGrid[24],currGrid[25],currGrid[26]};
assign sqrs[19] = {currGrid[0],currGrid[1],currGrid[2],currGrid[9],currGrid[10],currGrid[11],currGrid[18],currGrid[20]};
assign cols[20] = {currGrid[2],currGrid[11],currGrid[29],currGrid[38],currGrid[47],currGrid[56],currGrid[65],currGrid[74]};
assign rows[20] = {currGrid[18],currGrid[19],currGrid[21],currGrid[22],currGrid[23],currGrid[24],currGrid[25],currGrid[26]};
assign sqrs[20] = {currGrid[0],currGrid[1],currGrid[2],currGrid[9],currGrid[10],currGrid[11],currGrid[18],currGrid[19]};
assign cols[21] = {currGrid[3],currGrid[12],currGrid[30],currGrid[39],currGrid[48],currGrid[57],currGrid[66],currGrid[75]};
assign rows[21] = {currGrid[18],currGrid[19],currGrid[20],currGrid[22],currGrid[23],currGrid[24],currGrid[25],currGrid[26]};
assign sqrs[21] = {currGrid[3],currGrid[4],currGrid[5],currGrid[12],currGrid[13],currGrid[14],currGrid[22],currGrid[23]};
assign cols[22] = {currGrid[4],currGrid[13],currGrid[31],currGrid[40],currGrid[49],currGrid[58],currGrid[67],currGrid[76]};
assign rows[22] = {currGrid[18],currGrid[19],currGrid[20],currGrid[21],currGrid[23],currGrid[24],currGrid[25],currGrid[26]};
assign sqrs[22] = {currGrid[3],currGrid[4],currGrid[5],currGrid[12],currGrid[13],currGrid[14],currGrid[21],currGrid[23]};
assign cols[23] = {currGrid[5],currGrid[14],currGrid[32],currGrid[41],currGrid[50],currGrid[59],currGrid[68],currGrid[77]};
assign rows[23] = {currGrid[18],currGrid[19],currGrid[20],currGrid[21],currGrid[22],currGrid[24],currGrid[25],currGrid[26]};
assign sqrs[23] = {currGrid[3],currGrid[4],currGrid[5],currGrid[12],currGrid[13],currGrid[14],currGrid[21],currGrid[22]};
assign cols[24] = {currGrid[6],currGrid[15],currGrid[33],currGrid[42],currGrid[51],currGrid[60],currGrid[69],currGrid[78]};
assign rows[24] = {currGrid[18],currGrid[19],currGrid[20],currGrid[21],currGrid[22],currGrid[23],currGrid[25],currGrid[26]};
assign sqrs[24] = {currGrid[6],currGrid[7],currGrid[8],currGrid[15],currGrid[16],currGrid[17],currGrid[25],currGrid[26]};
assign cols[25] = {currGrid[7],currGrid[16],currGrid[34],currGrid[43],currGrid[52],currGrid[61],currGrid[70],currGrid[79]};
assign rows[25] = {currGrid[18],currGrid[19],currGrid[20],currGrid[21],currGrid[22],currGrid[23],currGrid[24],currGrid[26]};
assign sqrs[25] = {currGrid[6],currGrid[7],currGrid[8],currGrid[15],currGrid[16],currGrid[17],currGrid[24],currGrid[26]};
assign cols[26] = {currGrid[8],currGrid[17],currGrid[35],currGrid[44],currGrid[53],currGrid[62],currGrid[71],currGrid[80]};
assign rows[26] = {currGrid[18],currGrid[19],currGrid[20],currGrid[21],currGrid[22],currGrid[23],currGrid[24],currGrid[25]};
assign sqrs[26] = {currGrid[6],currGrid[7],currGrid[8],currGrid[15],currGrid[16],currGrid[17],currGrid[24],currGrid[25]};
assign cols[27] = {currGrid[0],currGrid[9],currGrid[18],currGrid[36],currGrid[45],currGrid[54],currGrid[63],currGrid[72]};
assign rows[27] = {currGrid[28],currGrid[29],currGrid[30],currGrid[31],currGrid[32],currGrid[33],currGrid[34],currGrid[35]};
assign sqrs[27] = {currGrid[28],currGrid[29],currGrid[36],currGrid[37],currGrid[38],currGrid[45],currGrid[46],currGrid[47]};
assign cols[28] = {currGrid[1],currGrid[10],currGrid[19],currGrid[37],currGrid[46],currGrid[55],currGrid[64],currGrid[73]};
assign rows[28] = {currGrid[27],currGrid[29],currGrid[30],currGrid[31],currGrid[32],currGrid[33],currGrid[34],currGrid[35]};
assign sqrs[28] = {currGrid[27],currGrid[29],currGrid[36],currGrid[37],currGrid[38],currGrid[45],currGrid[46],currGrid[47]};
assign cols[29] = {currGrid[2],currGrid[11],currGrid[20],currGrid[38],currGrid[47],currGrid[56],currGrid[65],currGrid[74]};
assign rows[29] = {currGrid[27],currGrid[28],currGrid[30],currGrid[31],currGrid[32],currGrid[33],currGrid[34],currGrid[35]};
assign sqrs[29] = {currGrid[27],currGrid[28],currGrid[36],currGrid[37],currGrid[38],currGrid[45],currGrid[46],currGrid[47]};
assign cols[30] = {currGrid[3],currGrid[12],currGrid[21],currGrid[39],currGrid[48],currGrid[57],currGrid[66],currGrid[75]};
assign rows[30] = {currGrid[27],currGrid[28],currGrid[29],currGrid[31],currGrid[32],currGrid[33],currGrid[34],currGrid[35]};
assign sqrs[30] = {currGrid[31],currGrid[32],currGrid[39],currGrid[40],currGrid[41],currGrid[48],currGrid[49],currGrid[50]};
assign cols[31] = {currGrid[4],currGrid[13],currGrid[22],currGrid[40],currGrid[49],currGrid[58],currGrid[67],currGrid[76]};
assign rows[31] = {currGrid[27],currGrid[28],currGrid[29],currGrid[30],currGrid[32],currGrid[33],currGrid[34],currGrid[35]};
assign sqrs[31] = {currGrid[30],currGrid[32],currGrid[39],currGrid[40],currGrid[41],currGrid[48],currGrid[49],currGrid[50]};
assign cols[32] = {currGrid[5],currGrid[14],currGrid[23],currGrid[41],currGrid[50],currGrid[59],currGrid[68],currGrid[77]};
assign rows[32] = {currGrid[27],currGrid[28],currGrid[29],currGrid[30],currGrid[31],currGrid[33],currGrid[34],currGrid[35]};
assign sqrs[32] = {currGrid[30],currGrid[31],currGrid[39],currGrid[40],currGrid[41],currGrid[48],currGrid[49],currGrid[50]};
assign cols[33] = {currGrid[6],currGrid[15],currGrid[24],currGrid[42],currGrid[51],currGrid[60],currGrid[69],currGrid[78]};
assign rows[33] = {currGrid[27],currGrid[28],currGrid[29],currGrid[30],currGrid[31],currGrid[32],currGrid[34],currGrid[35]};
assign sqrs[33] = {currGrid[34],currGrid[35],currGrid[42],currGrid[43],currGrid[44],currGrid[51],currGrid[52],currGrid[53]};
assign cols[34] = {currGrid[7],currGrid[16],currGrid[25],currGrid[43],currGrid[52],currGrid[61],currGrid[70],currGrid[79]};
assign rows[34] = {currGrid[27],currGrid[28],currGrid[29],currGrid[30],currGrid[31],currGrid[32],currGrid[33],currGrid[35]};
assign sqrs[34] = {currGrid[33],currGrid[35],currGrid[42],currGrid[43],currGrid[44],currGrid[51],currGrid[52],currGrid[53]};
assign cols[35] = {currGrid[8],currGrid[17],currGrid[26],currGrid[44],currGrid[53],currGrid[62],currGrid[71],currGrid[80]};
assign rows[35] = {currGrid[27],currGrid[28],currGrid[29],currGrid[30],currGrid[31],currGrid[32],currGrid[33],currGrid[34]};
assign sqrs[35] = {currGrid[33],currGrid[34],currGrid[42],currGrid[43],currGrid[44],currGrid[51],currGrid[52],currGrid[53]};
assign cols[36] = {currGrid[0],currGrid[9],currGrid[18],currGrid[27],currGrid[45],currGrid[54],currGrid[63],currGrid[72]};
assign rows[36] = {currGrid[37],currGrid[38],currGrid[39],currGrid[40],currGrid[41],currGrid[42],currGrid[43],currGrid[44]};
assign sqrs[36] = {currGrid[27],currGrid[28],currGrid[29],currGrid[37],currGrid[38],currGrid[45],currGrid[46],currGrid[47]};
assign cols[37] = {currGrid[1],currGrid[10],currGrid[19],currGrid[28],currGrid[46],currGrid[55],currGrid[64],currGrid[73]};
assign rows[37] = {currGrid[36],currGrid[38],currGrid[39],currGrid[40],currGrid[41],currGrid[42],currGrid[43],currGrid[44]};
assign sqrs[37] = {currGrid[27],currGrid[28],currGrid[29],currGrid[36],currGrid[38],currGrid[45],currGrid[46],currGrid[47]};
assign cols[38] = {currGrid[2],currGrid[11],currGrid[20],currGrid[29],currGrid[47],currGrid[56],currGrid[65],currGrid[74]};
assign rows[38] = {currGrid[36],currGrid[37],currGrid[39],currGrid[40],currGrid[41],currGrid[42],currGrid[43],currGrid[44]};
assign sqrs[38] = {currGrid[27],currGrid[28],currGrid[29],currGrid[36],currGrid[37],currGrid[45],currGrid[46],currGrid[47]};
assign cols[39] = {currGrid[3],currGrid[12],currGrid[21],currGrid[30],currGrid[48],currGrid[57],currGrid[66],currGrid[75]};
assign rows[39] = {currGrid[36],currGrid[37],currGrid[38],currGrid[40],currGrid[41],currGrid[42],currGrid[43],currGrid[44]};
assign sqrs[39] = {currGrid[30],currGrid[31],currGrid[32],currGrid[40],currGrid[41],currGrid[48],currGrid[49],currGrid[50]};
assign cols[40] = {currGrid[4],currGrid[13],currGrid[22],currGrid[31],currGrid[49],currGrid[58],currGrid[67],currGrid[76]};
assign rows[40] = {currGrid[36],currGrid[37],currGrid[38],currGrid[39],currGrid[41],currGrid[42],currGrid[43],currGrid[44]};
assign sqrs[40] = {currGrid[30],currGrid[31],currGrid[32],currGrid[39],currGrid[41],currGrid[48],currGrid[49],currGrid[50]};
assign cols[41] = {currGrid[5],currGrid[14],currGrid[23],currGrid[32],currGrid[50],currGrid[59],currGrid[68],currGrid[77]};
assign rows[41] = {currGrid[36],currGrid[37],currGrid[38],currGrid[39],currGrid[40],currGrid[42],currGrid[43],currGrid[44]};
assign sqrs[41] = {currGrid[30],currGrid[31],currGrid[32],currGrid[39],currGrid[40],currGrid[48],currGrid[49],currGrid[50]};
assign cols[42] = {currGrid[6],currGrid[15],currGrid[24],currGrid[33],currGrid[51],currGrid[60],currGrid[69],currGrid[78]};
assign rows[42] = {currGrid[36],currGrid[37],currGrid[38],currGrid[39],currGrid[40],currGrid[41],currGrid[43],currGrid[44]};
assign sqrs[42] = {currGrid[33],currGrid[34],currGrid[35],currGrid[43],currGrid[44],currGrid[51],currGrid[52],currGrid[53]};
assign cols[43] = {currGrid[7],currGrid[16],currGrid[25],currGrid[34],currGrid[52],currGrid[61],currGrid[70],currGrid[79]};
assign rows[43] = {currGrid[36],currGrid[37],currGrid[38],currGrid[39],currGrid[40],currGrid[41],currGrid[42],currGrid[44]};
assign sqrs[43] = {currGrid[33],currGrid[34],currGrid[35],currGrid[42],currGrid[44],currGrid[51],currGrid[52],currGrid[53]};
assign cols[44] = {currGrid[8],currGrid[17],currGrid[26],currGrid[35],currGrid[53],currGrid[62],currGrid[71],currGrid[80]};
assign rows[44] = {currGrid[36],currGrid[37],currGrid[38],currGrid[39],currGrid[40],currGrid[41],currGrid[42],currGrid[43]};
assign sqrs[44] = {currGrid[33],currGrid[34],currGrid[35],currGrid[42],currGrid[43],currGrid[51],currGrid[52],currGrid[53]};
assign cols[45] = {currGrid[0],currGrid[9],currGrid[18],currGrid[27],currGrid[36],currGrid[54],currGrid[63],currGrid[72]};
assign rows[45] = {currGrid[46],currGrid[47],currGrid[48],currGrid[49],currGrid[50],currGrid[51],currGrid[52],currGrid[53]};
assign sqrs[45] = {currGrid[27],currGrid[28],currGrid[29],currGrid[36],currGrid[37],currGrid[38],currGrid[46],currGrid[47]};
assign cols[46] = {currGrid[1],currGrid[10],currGrid[19],currGrid[28],currGrid[37],currGrid[55],currGrid[64],currGrid[73]};
assign rows[46] = {currGrid[45],currGrid[47],currGrid[48],currGrid[49],currGrid[50],currGrid[51],currGrid[52],currGrid[53]};
assign sqrs[46] = {currGrid[27],currGrid[28],currGrid[29],currGrid[36],currGrid[37],currGrid[38],currGrid[45],currGrid[47]};
assign cols[47] = {currGrid[2],currGrid[11],currGrid[20],currGrid[29],currGrid[38],currGrid[56],currGrid[65],currGrid[74]};
assign rows[47] = {currGrid[45],currGrid[46],currGrid[48],currGrid[49],currGrid[50],currGrid[51],currGrid[52],currGrid[53]};
assign sqrs[47] = {currGrid[27],currGrid[28],currGrid[29],currGrid[36],currGrid[37],currGrid[38],currGrid[45],currGrid[46]};
assign cols[48] = {currGrid[3],currGrid[12],currGrid[21],currGrid[30],currGrid[39],currGrid[57],currGrid[66],currGrid[75]};
assign rows[48] = {currGrid[45],currGrid[46],currGrid[47],currGrid[49],currGrid[50],currGrid[51],currGrid[52],currGrid[53]};
assign sqrs[48] = {currGrid[30],currGrid[31],currGrid[32],currGrid[39],currGrid[40],currGrid[41],currGrid[49],currGrid[50]};
assign cols[49] = {currGrid[4],currGrid[13],currGrid[22],currGrid[31],currGrid[40],currGrid[58],currGrid[67],currGrid[76]};
assign rows[49] = {currGrid[45],currGrid[46],currGrid[47],currGrid[48],currGrid[50],currGrid[51],currGrid[52],currGrid[53]};
assign sqrs[49] = {currGrid[30],currGrid[31],currGrid[32],currGrid[39],currGrid[40],currGrid[41],currGrid[48],currGrid[50]};
assign cols[50] = {currGrid[5],currGrid[14],currGrid[23],currGrid[32],currGrid[41],currGrid[59],currGrid[68],currGrid[77]};
assign rows[50] = {currGrid[45],currGrid[46],currGrid[47],currGrid[48],currGrid[49],currGrid[51],currGrid[52],currGrid[53]};
assign sqrs[50] = {currGrid[30],currGrid[31],currGrid[32],currGrid[39],currGrid[40],currGrid[41],currGrid[48],currGrid[49]};
assign cols[51] = {currGrid[6],currGrid[15],currGrid[24],currGrid[33],currGrid[42],currGrid[60],currGrid[69],currGrid[78]};
assign rows[51] = {currGrid[45],currGrid[46],currGrid[47],currGrid[48],currGrid[49],currGrid[50],currGrid[52],currGrid[53]};
assign sqrs[51] = {currGrid[33],currGrid[34],currGrid[35],currGrid[42],currGrid[43],currGrid[44],currGrid[52],currGrid[53]};
assign cols[52] = {currGrid[7],currGrid[16],currGrid[25],currGrid[34],currGrid[43],currGrid[61],currGrid[70],currGrid[79]};
assign rows[52] = {currGrid[45],currGrid[46],currGrid[47],currGrid[48],currGrid[49],currGrid[50],currGrid[51],currGrid[53]};
assign sqrs[52] = {currGrid[33],currGrid[34],currGrid[35],currGrid[42],currGrid[43],currGrid[44],currGrid[51],currGrid[53]};
assign cols[53] = {currGrid[8],currGrid[17],currGrid[26],currGrid[35],currGrid[44],currGrid[62],currGrid[71],currGrid[80]};
assign rows[53] = {currGrid[45],currGrid[46],currGrid[47],currGrid[48],currGrid[49],currGrid[50],currGrid[51],currGrid[52]};
assign sqrs[53] = {currGrid[33],currGrid[34],currGrid[35],currGrid[42],currGrid[43],currGrid[44],currGrid[51],currGrid[52]};
assign cols[54] = {currGrid[0],currGrid[9],currGrid[18],currGrid[27],currGrid[36],currGrid[45],currGrid[63],currGrid[72]};
assign rows[54] = {currGrid[55],currGrid[56],currGrid[57],currGrid[58],currGrid[59],currGrid[60],currGrid[61],currGrid[62]};
assign sqrs[54] = {currGrid[55],currGrid[56],currGrid[63],currGrid[64],currGrid[65],currGrid[72],currGrid[73],currGrid[74]};
assign cols[55] = {currGrid[1],currGrid[10],currGrid[19],currGrid[28],currGrid[37],currGrid[46],currGrid[64],currGrid[73]};
assign rows[55] = {currGrid[54],currGrid[56],currGrid[57],currGrid[58],currGrid[59],currGrid[60],currGrid[61],currGrid[62]};
assign sqrs[55] = {currGrid[54],currGrid[56],currGrid[63],currGrid[64],currGrid[65],currGrid[72],currGrid[73],currGrid[74]};
assign cols[56] = {currGrid[2],currGrid[11],currGrid[20],currGrid[29],currGrid[38],currGrid[47],currGrid[65],currGrid[74]};
assign rows[56] = {currGrid[54],currGrid[55],currGrid[57],currGrid[58],currGrid[59],currGrid[60],currGrid[61],currGrid[62]};
assign sqrs[56] = {currGrid[54],currGrid[55],currGrid[63],currGrid[64],currGrid[65],currGrid[72],currGrid[73],currGrid[74]};
assign cols[57] = {currGrid[3],currGrid[12],currGrid[21],currGrid[30],currGrid[39],currGrid[48],currGrid[66],currGrid[75]};
assign rows[57] = {currGrid[54],currGrid[55],currGrid[56],currGrid[58],currGrid[59],currGrid[60],currGrid[61],currGrid[62]};
assign sqrs[57] = {currGrid[58],currGrid[59],currGrid[66],currGrid[67],currGrid[68],currGrid[75],currGrid[76],currGrid[77]};
assign cols[58] = {currGrid[4],currGrid[13],currGrid[22],currGrid[31],currGrid[40],currGrid[49],currGrid[67],currGrid[76]};
assign rows[58] = {currGrid[54],currGrid[55],currGrid[56],currGrid[57],currGrid[59],currGrid[60],currGrid[61],currGrid[62]};
assign sqrs[58] = {currGrid[57],currGrid[59],currGrid[66],currGrid[67],currGrid[68],currGrid[75],currGrid[76],currGrid[77]};
assign cols[59] = {currGrid[5],currGrid[14],currGrid[23],currGrid[32],currGrid[41],currGrid[50],currGrid[68],currGrid[77]};
assign rows[59] = {currGrid[54],currGrid[55],currGrid[56],currGrid[57],currGrid[58],currGrid[60],currGrid[61],currGrid[62]};
assign sqrs[59] = {currGrid[57],currGrid[58],currGrid[66],currGrid[67],currGrid[68],currGrid[75],currGrid[76],currGrid[77]};
assign cols[60] = {currGrid[6],currGrid[15],currGrid[24],currGrid[33],currGrid[42],currGrid[51],currGrid[69],currGrid[78]};
assign rows[60] = {currGrid[54],currGrid[55],currGrid[56],currGrid[57],currGrid[58],currGrid[59],currGrid[61],currGrid[62]};
assign sqrs[60] = {currGrid[61],currGrid[62],currGrid[69],currGrid[70],currGrid[71],currGrid[78],currGrid[79],currGrid[80]};
assign cols[61] = {currGrid[7],currGrid[16],currGrid[25],currGrid[34],currGrid[43],currGrid[52],currGrid[70],currGrid[79]};
assign rows[61] = {currGrid[54],currGrid[55],currGrid[56],currGrid[57],currGrid[58],currGrid[59],currGrid[60],currGrid[62]};
assign sqrs[61] = {currGrid[60],currGrid[62],currGrid[69],currGrid[70],currGrid[71],currGrid[78],currGrid[79],currGrid[80]};
assign cols[62] = {currGrid[8],currGrid[17],currGrid[26],currGrid[35],currGrid[44],currGrid[53],currGrid[71],currGrid[80]};
assign rows[62] = {currGrid[54],currGrid[55],currGrid[56],currGrid[57],currGrid[58],currGrid[59],currGrid[60],currGrid[61]};
assign sqrs[62] = {currGrid[60],currGrid[61],currGrid[69],currGrid[70],currGrid[71],currGrid[78],currGrid[79],currGrid[80]};
assign cols[63] = {currGrid[0],currGrid[9],currGrid[18],currGrid[27],currGrid[36],currGrid[45],currGrid[54],currGrid[72]};
assign rows[63] = {currGrid[64],currGrid[65],currGrid[66],currGrid[67],currGrid[68],currGrid[69],currGrid[70],currGrid[71]};
assign sqrs[63] = {currGrid[54],currGrid[55],currGrid[56],currGrid[64],currGrid[65],currGrid[72],currGrid[73],currGrid[74]};
assign cols[64] = {currGrid[1],currGrid[10],currGrid[19],currGrid[28],currGrid[37],currGrid[46],currGrid[55],currGrid[73]};
assign rows[64] = {currGrid[63],currGrid[65],currGrid[66],currGrid[67],currGrid[68],currGrid[69],currGrid[70],currGrid[71]};
assign sqrs[64] = {currGrid[54],currGrid[55],currGrid[56],currGrid[63],currGrid[65],currGrid[72],currGrid[73],currGrid[74]};
assign cols[65] = {currGrid[2],currGrid[11],currGrid[20],currGrid[29],currGrid[38],currGrid[47],currGrid[56],currGrid[74]};
assign rows[65] = {currGrid[63],currGrid[64],currGrid[66],currGrid[67],currGrid[68],currGrid[69],currGrid[70],currGrid[71]};
assign sqrs[65] = {currGrid[54],currGrid[55],currGrid[56],currGrid[63],currGrid[64],currGrid[72],currGrid[73],currGrid[74]};
assign cols[66] = {currGrid[3],currGrid[12],currGrid[21],currGrid[30],currGrid[39],currGrid[48],currGrid[57],currGrid[75]};
assign rows[66] = {currGrid[63],currGrid[64],currGrid[65],currGrid[67],currGrid[68],currGrid[69],currGrid[70],currGrid[71]};
assign sqrs[66] = {currGrid[57],currGrid[58],currGrid[59],currGrid[67],currGrid[68],currGrid[75],currGrid[76],currGrid[77]};
assign cols[67] = {currGrid[4],currGrid[13],currGrid[22],currGrid[31],currGrid[40],currGrid[49],currGrid[58],currGrid[76]};
assign rows[67] = {currGrid[63],currGrid[64],currGrid[65],currGrid[66],currGrid[68],currGrid[69],currGrid[70],currGrid[71]};
assign sqrs[67] = {currGrid[57],currGrid[58],currGrid[59],currGrid[66],currGrid[68],currGrid[75],currGrid[76],currGrid[77]};
assign cols[68] = {currGrid[5],currGrid[14],currGrid[23],currGrid[32],currGrid[41],currGrid[50],currGrid[59],currGrid[77]};
assign rows[68] = {currGrid[63],currGrid[64],currGrid[65],currGrid[66],currGrid[67],currGrid[69],currGrid[70],currGrid[71]};
assign sqrs[68] = {currGrid[57],currGrid[58],currGrid[59],currGrid[66],currGrid[67],currGrid[75],currGrid[76],currGrid[77]};
assign cols[69] = {currGrid[6],currGrid[15],currGrid[24],currGrid[33],currGrid[42],currGrid[51],currGrid[60],currGrid[78]};
assign rows[69] = {currGrid[63],currGrid[64],currGrid[65],currGrid[66],currGrid[67],currGrid[68],currGrid[70],currGrid[71]};
assign sqrs[69] = {currGrid[60],currGrid[61],currGrid[62],currGrid[70],currGrid[71],currGrid[78],currGrid[79],currGrid[80]};
assign cols[70] = {currGrid[7],currGrid[16],currGrid[25],currGrid[34],currGrid[43],currGrid[52],currGrid[61],currGrid[79]};
assign rows[70] = {currGrid[63],currGrid[64],currGrid[65],currGrid[66],currGrid[67],currGrid[68],currGrid[69],currGrid[71]};
assign sqrs[70] = {currGrid[60],currGrid[61],currGrid[62],currGrid[69],currGrid[71],currGrid[78],currGrid[79],currGrid[80]};
assign cols[71] = {currGrid[8],currGrid[17],currGrid[26],currGrid[35],currGrid[44],currGrid[53],currGrid[62],currGrid[80]};
assign rows[71] = {currGrid[63],currGrid[64],currGrid[65],currGrid[66],currGrid[67],currGrid[68],currGrid[69],currGrid[70]};
assign sqrs[71] = {currGrid[60],currGrid[61],currGrid[62],currGrid[69],currGrid[70],currGrid[78],currGrid[79],currGrid[80]};
assign cols[72] = {currGrid[0],currGrid[9],currGrid[18],currGrid[27],currGrid[36],currGrid[45],currGrid[54],currGrid[63]};
assign rows[72] = {currGrid[73],currGrid[74],currGrid[75],currGrid[76],currGrid[77],currGrid[78],currGrid[79],currGrid[80]};
assign sqrs[72] = {currGrid[54],currGrid[55],currGrid[56],currGrid[63],currGrid[64],currGrid[65],currGrid[73],currGrid[74]};
assign cols[73] = {currGrid[1],currGrid[10],currGrid[19],currGrid[28],currGrid[37],currGrid[46],currGrid[55],currGrid[64]};
assign rows[73] = {currGrid[72],currGrid[74],currGrid[75],currGrid[76],currGrid[77],currGrid[78],currGrid[79],currGrid[80]};
assign sqrs[73] = {currGrid[54],currGrid[55],currGrid[56],currGrid[63],currGrid[64],currGrid[65],currGrid[72],currGrid[74]};
assign cols[74] = {currGrid[2],currGrid[11],currGrid[20],currGrid[29],currGrid[38],currGrid[47],currGrid[56],currGrid[65]};
assign rows[74] = {currGrid[72],currGrid[73],currGrid[75],currGrid[76],currGrid[77],currGrid[78],currGrid[79],currGrid[80]};
assign sqrs[74] = {currGrid[54],currGrid[55],currGrid[56],currGrid[63],currGrid[64],currGrid[65],currGrid[72],currGrid[73]};
assign cols[75] = {currGrid[3],currGrid[12],currGrid[21],currGrid[30],currGrid[39],currGrid[48],currGrid[57],currGrid[66]};
assign rows[75] = {currGrid[72],currGrid[73],currGrid[74],currGrid[76],currGrid[77],currGrid[78],currGrid[79],currGrid[80]};
assign sqrs[75] = {currGrid[57],currGrid[58],currGrid[59],currGrid[66],currGrid[67],currGrid[68],currGrid[76],currGrid[77]};
assign cols[76] = {currGrid[4],currGrid[13],currGrid[22],currGrid[31],currGrid[40],currGrid[49],currGrid[58],currGrid[67]};
assign rows[76] = {currGrid[72],currGrid[73],currGrid[74],currGrid[75],currGrid[77],currGrid[78],currGrid[79],currGrid[80]};
assign sqrs[76] = {currGrid[57],currGrid[58],currGrid[59],currGrid[66],currGrid[67],currGrid[68],currGrid[75],currGrid[77]};
assign cols[77] = {currGrid[5],currGrid[14],currGrid[23],currGrid[32],currGrid[41],currGrid[50],currGrid[59],currGrid[68]};
assign rows[77] = {currGrid[72],currGrid[73],currGrid[74],currGrid[75],currGrid[76],currGrid[78],currGrid[79],currGrid[80]};
assign sqrs[77] = {currGrid[57],currGrid[58],currGrid[59],currGrid[66],currGrid[67],currGrid[68],currGrid[75],currGrid[76]};
assign cols[78] = {currGrid[6],currGrid[15],currGrid[24],currGrid[33],currGrid[42],currGrid[51],currGrid[60],currGrid[69]};
assign rows[78] = {currGrid[72],currGrid[73],currGrid[74],currGrid[75],currGrid[76],currGrid[77],currGrid[79],currGrid[80]};
assign sqrs[78] = {currGrid[60],currGrid[61],currGrid[62],currGrid[69],currGrid[70],currGrid[71],currGrid[79],currGrid[80]};
assign cols[79] = {currGrid[7],currGrid[16],currGrid[25],currGrid[34],currGrid[43],currGrid[52],currGrid[61],currGrid[70]};
assign rows[79] = {currGrid[72],currGrid[73],currGrid[74],currGrid[75],currGrid[76],currGrid[77],currGrid[78],currGrid[80]};
assign sqrs[79] = {currGrid[60],currGrid[61],currGrid[62],currGrid[69],currGrid[70],currGrid[71],currGrid[78],currGrid[80]};
assign cols[80] = {currGrid[8],currGrid[17],currGrid[26],currGrid[35],currGrid[44],currGrid[53],currGrid[62],currGrid[71]};
assign rows[80] = {currGrid[72],currGrid[73],currGrid[74],currGrid[75],currGrid[76],currGrid[77],currGrid[78],currGrid[79]};
assign sqrs[80] = {currGrid[60],currGrid[61],currGrid[62],currGrid[69],currGrid[70],currGrid[71],currGrid[78],currGrid[79]};
 
generate
for(i=0;i<81;i=i+1)
begin: outGridGen
assign outGrid[(9*(i+1)-1):(9*i)] = currGrid[i];
 
end
endgenerate
genvar ii,jj;
wire [80:0] c_rows [8:0];
wire [80:0] c_cols [8:0];
wire [80:0] c_grds [8:0];
wire [26:0] w_correct;
generate
for(ii=0;ii<9;ii=ii+1)
begin: row_check
assign c_rows[0][(9*(ii+1)-1):9*ii] = currGrid[ii];
assign c_rows[1][(9*(ii+1)-1):9*ii] = currGrid[9+ii];
assign c_rows[2][(9*(ii+1)-1):9*ii] = currGrid[18+ii];
assign c_rows[3][(9*(ii+1)-1):9*ii] = currGrid[27+ii];
assign c_rows[4][(9*(ii+1)-1):9*ii] = currGrid[36+ii];
assign c_rows[5][(9*(ii+1)-1):9*ii] = currGrid[45+ii];
assign c_rows[6][(9*(ii+1)-1):9*ii] = currGrid[54+ii];
assign c_rows[7][(9*(ii+1)-1):9*ii] = currGrid[63+ii];
assign c_rows[8][(9*(ii+1)-1):9*ii] = currGrid[72+ii];
end
endgenerate
generate
for(ii=0;ii<9;ii=ii+1)
begin: col_check
assign c_cols[0][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 0];
assign c_cols[1][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 1];
assign c_cols[2][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 2];
assign c_cols[3][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 3];
assign c_cols[4][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 4];
assign c_cols[5][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 5];
assign c_cols[6][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 6];
assign c_cols[7][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 7];
assign c_cols[8][(9*(ii+1)-1):9*ii] = currGrid[9*ii + 8];
end
endgenerate
 
genvar iii,jjj;
generate
for(ii=0; ii < 3; ii=ii+1)
begin: grd_check_y
for(jj = 0; jj < 3; jj=jj+1)
begin: grd_check_x
for(iii=3*ii; iii < 3*(ii+1); iii=iii+1)
begin: gg_y
for(jjj=3*jj; jjj < 3*(jj+1); jjj=jjj+1)
begin: gg_x
//(3*(iii-3*ii) + (jjj-3*jj))
assign c_grds[3*ii+jj][9*(3*(iii-3*ii) + (jjj-3*jj)+1)-1:9*(3*(iii-3*ii) + (jjj-3*jj))] = currGrid[9*iii + jjj];
end
end
end
end
endgenerate
generate
for(ii=0;ii<9;ii=ii+1)
begin: checks
checkCorrect cC_R (.y(w_correct[ii]), .in(c_rows[ii]));
checkCorrect cC_C (.y(w_correct[9+ii]), .in(c_cols[ii]));
checkCorrect cC_G (.y(w_correct[18+ii]), .in(c_grds[ii]));
end
endgenerate
//assign anyError = ~(&w_correct);
 
always@(posedge clk)
begin
if(rst)
begin
r_done <= 1'b0;
r_changed <= 1'b0;
r_error <= 1'b0;
end
else
begin
r_done <= start ? 1'b0 : &done;
r_changed <= start ? 1'b0 : |changed;
r_error <= start ? 1'b0 : ~(&w_correct);
end
end
 
endmodule
/sudoku/branches/zynq/sw/driver.h
0,0 → 1,63
#ifndef _DRIVER_H
#define _DRIVER_H
 
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
#include <assert.h>
#include <stdio.h>
#include <sys/mman.h>
 
class Driver
{
public:
Driver(uintptr_t paddr)
{
this->paddr = paddr;
uintptr_t pgsize = sysconf(_SC_PAGESIZE);
uintptr_t regsize = regs * sizeof(uintptr_t);
uintptr_t memsize = (regsize-1)/pgsize*pgsize+1;
 
/*printf("opening interface at %p\n", (void*)paddr);*/
 
int fd = open("/dev/mem", O_RDWR | O_SYNC);
assert(fd != -1);
 
int prot = PROT_READ | PROT_WRITE;
int flags = MAP_SHARED;
vaddr = (uintptr_t)mmap(0, memsize, prot, flags, fd, paddr & ~(pgsize-1));
assert((void*)vaddr != MAP_FAILED);
vaddr = vaddr + (paddr & (pgsize-1));
}
 
void reset()
{
*(volatile uintptr_t*)(vaddr + 0x100) = 0xA;
}
 
uintptr_t read(int port)
{
return *reg_addr(port);
}
 
void write(int port, uintptr_t value)
{
*reg_addr(port) = value;
}
 
int num_ports() {
return regs;
}
 
private:
uintptr_t vaddr;
uintptr_t paddr;
static const int regs = 8;
 
volatile uintptr_t* reg_addr(int port)
{
return (volatile uintptr_t*)vaddr + (regs - port - 1);
}
};
 
#endif
/sudoku/branches/zynq/sw/counters.cc
0,0 → 1,60
 
#include "counters.h"
 
static void initCounter(hwCounter_t &x, uint64_t counterConfig)
{
if(!x.init)
{
memset(&(x.attr), 0, sizeof(x.attr));
x.attr.disabled = 0;
x.attr.type = PERF_TYPE_HARDWARE;
x.attr.config = counterConfig;
pid_t pid = 0;
int cpu = -1;
int group_fd = -1;
unsigned long flags = 0;
x.fd = syscall(__NR_perf_event_open, &(x.attr), pid,
cpu, group_fd, flags);
assert(x.fd >= 0);
x.init = true;
}
}
 
void initTicks(hwCounter_t &x)
{
initCounter(x,PERF_COUNT_HW_CPU_CYCLES);
}
void initInsns(hwCounter_t &x)
{
initCounter(x,PERF_COUNT_HW_INSTRUCTIONS);
}
 
uint64_t getTicks(hwCounter_t &x)
{
int rc;
 
if(!x.init)
{
initTicks(x);
}
rc = read(x.fd,&(x.buffer),sizeof(x.buffer));
assert(rc == sizeof(x.buffer));
return x.buffer;
}
 
 
 
uint64_t getInsns(hwCounter_t &x)
{
int rc;
 
if(!x.init)
{
initInsns(x);
}
rc = read(x.fd,&(x.buffer),sizeof(x.buffer));
assert(rc == sizeof(x.buffer));
return x.buffer;
}
/sudoku/branches/zynq/sw/counters.h
0,0 → 1,28
#ifndef __COUNTERS_H__
#define __COUNTERS_H__
 
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <errno.h>
#include <unistd.h>
#include <cassert>
#include <sys/syscall.h>
#include <linux/perf_event.h>
#include <stdint.h>
 
typedef struct
{
bool init;
int fd;
struct perf_event_attr attr;
uint64_t buffer;
} hwCounter_t;
 
void initTicks(hwCounter_t &x);
void initInsns(hwCounter_t &x);
 
uint64_t getTicks(hwCounter_t &x);
uint64_t getInsns(hwCounter_t &x);
 
#endif
/sudoku/branches/zynq/sw/main.cc
0,0 → 1,641
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <time.h>
#include <limits.h>
#include <stdint.h>
#include <sys/time.h>
#include <unistd.h>
 
#include "driver.h"
#include "counters.h"
 
#define USE_DIV_TABLE 1
const int divTable[9] = {0,0,0,3,3,3,6,6,6};
 
double timestamp()
{
struct timeval tv;
gettimeofday (&tv, 0);
return tv.tv_sec + 1e-6*tv.tv_usec;
}
 
int32_t sudoku(uint32_t *board, uint32_t *os);
 
int u32_cmp(const void* a, const void *b)
{
uint32_t x = *((uint32_t*)a);
uint32_t y = *((uint32_t*)b);
return (x<y);
}
 
inline uint32_t ln2(uint32_t x)
{
uint32_t y = 1;
while(x > 1)
{
y++;
x = x>>1;
}
return y;
}
 
inline uint32_t one_set(uint32_t x)
{
/* all ones if pow2, otherwise 0 */
uint32_t pow2 = (x & (x-1));
uint32_t m = (pow2 == 0);
return ((~m) + 1) & x;
}
 
inline uint32_t find_first_set(uint32_t x)
{
#ifdef __GNUC__
return __builtin_ctz(x);
#else
/* copied from the sparc v9 reference manual */
return count_ones(x ^ (~(-x))) - 1;
#endif
}
 
inline uint32_t count_ones(uint32_t x)
{
#ifdef __GNUC__
return __builtin_popcount(x);
#else
uint32_t y = 0;
for(y=0;x!=0;y++)
{
x &= (x-1);
}
return y;
#endif
}
 
inline uint32_t isPow2(uint32_t x)
{
uint32_t pow2 = (x & (x-1));
return (pow2 == 0);
}
 
int32_t check_correct(uint32_t *board, uint32_t *unsolved_pieces)
{
int32_t i,j;
int32_t ii,jj;
int32_t si,sj;
int32_t tmp;
 
*unsolved_pieces = 0;
int32_t violated = 0;
 
uint32_t counts[81];
for(i=0;i < 81; i++)
{
counts[i] = count_ones(board[i]);
if(counts[i]!=1)
{
*unsolved_pieces = 1;
return 0;
}
}
 
/* for each row */
for(i=0;i<9;i++)
{
uint32_t sums[9] = {0};
for(j=0;j<9;j++)
{
if(counts[i*9 +j] == 1)
{
tmp =ln2(board[i*9+j])-1;
sums[tmp]++;
if(sums[tmp] > 1)
{
//char buf[80];
//sprintf_binary(board[i*9+j],buf,80);
//printf("violated row %d, sums[%d]=%d, board = %s\n", i, tmp, sums[tmp], buf);
//print_board(board);
violated = 1;
goto done;
}
}
}
}
/* for each column */
 
for(j=0;j<9;j++)
{
uint32_t sums[9] = {0};
for(i=0;i<9;i++)
{
if(counts[i*9 +j] == 1)
{
tmp =ln2(board[i*9+j])-1;
sums[tmp]++;
if(sums[tmp] > 1)
{
violated = 1;
goto done;
//printf("violated column %d, sums[%d]=%d\n", i, tmp, sums[tmp]);
//return 0;
}
}
}
}
 
for(i=0;i<9;i++)
{
#ifdef USE_DIV_TABLE
si = divTable[i];
#else
si = 3*(i/3);
#endif
for(j=0;j<9;j++)
{
#ifdef USE_DIV_TABLE
sj = 3*(j/3);
#else
sj = divTable[j];
#endif
uint32_t sums[9] = {0};
for(ii=si;ii<(si+3);ii++)
{
for(jj=sj;jj<(sj+3);jj++)
{
if(counts[ii*9 +jj] == 1)
{
tmp =ln2(board[ii*9+jj])-1;
sums[tmp]++;
if(sums[tmp] > 1)
{
violated = 1;
goto done;
}
}
}
}
}
}
 
done:
return (violated == 0);
}
 
 
 
void print_board(uint32_t *board)
{
int32_t i,j;
char buf[80] = {0};
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
/* sprintf_binary(board[i*9+j], buf, 80);
* printf("%s ", buf); */
printf("%d ", ln2(board[i*9+j]));
}
printf("\n");
}
printf("\n");
}
 
 
int32_t hw_solve(Driver *d, uint32_t *board)
{
uint32_t rc=0;
d->reset();
const uint32_t w_bit = 1 << 31;
 
/*
if(init == 0)
{
memset(&cCnt,0,sizeof(cCnt));
initTicks(cCnt);
init = 1;
}
*/
//uint64_t c0 = getTicks(cCnt);
for(int i = 0; i < 81; i++)
{
uint32_t addr = i;
uint32_t data = board[i];
uint32_t v = w_bit | (data << 7) | addr;
d->write(1, v);
}
//c0 = getTicks(cCnt) - c0;
//printf("%llu cycles to write data to FPGA\n", c0);
 
/* only pulsed for one cycle */
d->write(7,1);
 
do
{
rc = d->read(0) & 0x7;
}
while(rc ==0);
//c0 = getTicks(cCnt);
for(int i = 0; i < 81; i++)
{
uint32_t addr = i;
d->write(1, addr);
uint32_t v = d->read(2);
board[i] = v;
}
//c0 = getTicks(cCnt) - c0;
//printf("%llu cycles to read data from FPGA\n", c0);
return (rc == 0x1);
}
 
int main(int argc, char **argv)
{
uint32_t *cpuBoard, *hwBoard;
uint32_t *os;
uint64_t c0,c1,i0;
int i,j,rc;
uint32_t **puzzles;
uint32_t **cpyPuzzles;
uint32_t nPuzzles = 0;
uint32_t *speedUps = 0;
int c;
 
hwCounter_t cCnt,iCnt;
memset(&cCnt,0,sizeof(cCnt));
memset(&iCnt,0,sizeof(iCnt));
initTicks(cCnt);
initInsns(iCnt);
 
Driver *d = new Driver(0x79100000);
 
FILE *fp = 0;
 
if(argc < 2)
return -1;
 
fp = fopen(argv[1], "r");
assert(fp);
 
 
while((c = fgetc(fp)) != EOF)
{
if(c == '\n')
{
nPuzzles++;
}
}
rewind(fp);
puzzles = (uint32_t**)malloc(sizeof(uint32_t*)*nPuzzles);
cpyPuzzles = (uint32_t**)malloc(sizeof(uint32_t*)*nPuzzles);
speedUps = (uint32_t*)malloc(sizeof(uint32_t)*nPuzzles);
memset(speedUps,0,sizeof(uint32_t)*nPuzzles);
 
for(i=0;i<nPuzzles;i++)
{
puzzles[i] = (uint32_t*)malloc(sizeof(uint32_t)*81);
cpyPuzzles[i] = (uint32_t*)malloc(sizeof(uint32_t)*81);
}
 
j = i = 0;
while((c = fgetc(fp)) != EOF)
{
if(c == '\n')
{
j = 0;
i++;
}
else if(c == ' ')
{
continue;
}
else if(c == '.')
{
puzzles[i][j++] = 0x1ff;
}
else
{
if(c >= 65 && c <= 70)
{
c -= 55;
}
else
{
c -= 48;
}
puzzles[i][j++] = 1 << (c-1);
}
}
fclose(fp);
for(i=0;i<nPuzzles;i++)
{
memcpy(cpyPuzzles[i], puzzles[i], sizeof(uint32_t)*81);
}
 
printf("nPuzzles=%d\n", nPuzzles);
cpuBoard = (uint32_t*)malloc(sizeof(uint32_t)*81);
hwBoard = (uint32_t*)malloc(sizeof(uint32_t)*81);
os = (uint32_t*)malloc(sizeof(uint32_t)*81);
uint32_t mismatches = 0;
double t0,t1;
for(i=0;i<nPuzzles;i++)
{
c0 = c1 = 1;
t0 = t1 = 0.0;
memcpy(cpuBoard,puzzles[i],sizeof(uint32_t)*81);
memcpy(hwBoard,puzzles[i],sizeof(uint32_t)*81);
 
c0 = getTicks(cCnt);
i0 = getInsns(iCnt);
c = sudoku(cpuBoard, os);
i0 = getInsns(iCnt) - i0;
c0 = getTicks(cCnt) - c0;
double ipc = ((double)i0) / ((double)c0);
 
c1 = getTicks(cCnt);
rc = hw_solve(d,hwBoard);
c1 = getTicks(cCnt) - c1;
 
speedUps[i] = c0/c1;
printf("SpeedUp = %llu (%d) : SW ticks = %llu (IPC = %g), HW ticks = %llu\n",
c0/c1, c, c0, ipc, c1);
if(rc != 1)
{
printf("error with puzzle %d\n", i);
//print_board(puzzles[i]);
}
 
for(j=0;j<81;j++)
{
if(cpuBoard[j]!=hwBoard[j])
{
mismatches++;
break;
}
}
//print_board(puzzles[i]);
}
 
done:
printf("%u mismatches between CPU and FPGA\n", mismatches);
qsort(speedUps, nPuzzles, sizeof(uint32_t), u32_cmp);
c = rand()%nPuzzles;
for(i=0;i<nPuzzles;i++)
{
memcpy(puzzles[i], cpyPuzzles[i], sizeof(uint32_t)*81);
}
 
t1 = timestamp();
for(i=0;i<nPuzzles;i++)
{
sudoku(puzzles[i],os);
}
t1 = timestamp() - t1;
printf("%d\n", puzzles[c][0]);
for(i=0;i<nPuzzles;i++)
{
memcpy(puzzles[i], cpyPuzzles[i], sizeof(uint32_t)*81);
}
 
t0 = timestamp();
for(i=0;i<nPuzzles;i++)
{
hw_solve(d,puzzles[i]);
}
t0 = timestamp() - t0;
 
printf("%d\n", puzzles[c][0]);
 
printf("HW=%g,SW=%g\n", t0, t1);
if(nPuzzles == 1)
{
print_board(puzzles[0]);
}
 
if(nPuzzles > 0)
{
printf("Speed-Ups: Median = %u, Max=%u, Min=%u\n",
speedUps[nPuzzles/2],
speedUps[0],
speedUps[nPuzzles-1]
);
}
for(i=0;i<nPuzzles;i++)
{
free(cpyPuzzles[i]);
free(puzzles[i]);
}
free(cpyPuzzles);
free(puzzles);
 
delete d;
free(os);
free(cpuBoard);
free(hwBoard);
free(speedUps);
return 0;
}
 
int32_t solve(uint32_t *board, uint32_t *os)
{
int32_t i,j,idx;
int32_t ii,jj;
int32_t ib,jb;
uint32_t set_row, set_col, set_sqr;
uint32_t row_or, col_or, sqr_or;
uint32_t tmp;
int32_t changed = 0;
do
{
changed=0;
//print_board(board);
/* compute all positions one's set value */
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
{
idx = i*9 + j;
os[idx] = one_set(board[idx]);
}
}
 
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
{
/* already solved */
if(isPow2(board[i*9+j]))
continue;
else if(board[idx]==0)
return 0;
 
row_or = set_row = 0;
for(jj = 0; jj < 9; jj++)
{
idx = i*9 + jj;
if(jj == j)
continue;
set_row |= os[idx];
row_or |= board[idx];
}
col_or = set_col = 0;
for(ii = 0; ii < 9; ii++)
{
idx = ii*9 + j;
if(ii == i)
continue;
set_col |= os[idx];
col_or |= board[idx];
}
sqr_or = set_sqr = 0;
#ifdef USE_DIV_TABLE
ib = divTable[i];
jb = divTable[j];
#else
ib = 3*(i/3);
jb = 3*(j/3);
#endif
for(ii=ib;ii < ib+3;ii++)
{
for(jj=jb;jj<jb+3;jj++)
{
idx = ii*9 + jj;
if((i==ii) && (j == jj))
continue;
set_sqr |= os[idx];
sqr_or |= board[idx];
}
}
tmp = board[i*9 + j] & ~( set_row | set_col | set_sqr);
if(tmp != board[i*9 + j])
{
changed = 1;
}
board[i*9+j] = tmp;
 
/* check for singletons */
tmp = 0;
tmp = one_set(board[i*9 + j] & (~row_or));
tmp |= one_set(board[i*9 + j] & (~col_or));
tmp |= one_set(board[i*9 + j] & (~sqr_or));
if(tmp != 0 && (board[i*9+j] != tmp))
{
board[i*9+j] = tmp;
changed = 1;
}
}
}
} while(changed);
 
return 0;
}
 
inline void find_min(uint32_t *board, int32_t *min_idx, int *min_pos)
{
int32_t tmp,idx,i,j;
int32_t tmin_idx,tmin_pos;
tmin_idx = 0;
tmin_pos = INT_MAX;
for(idx=0;idx<81;idx++)
{
tmp = count_ones(board[idx]);
tmp = (tmp == 1) ? INT_MAX : tmp;
if(tmp < tmin_pos)
{
tmin_pos = tmp;
tmin_idx = idx;
}
}
*min_idx = tmin_idx;
*min_pos = tmin_pos;
}
 
int32_t sudoku(uint32_t *board, uint32_t *os)
{
int32_t rc;
int32_t itrs=0;
int32_t tmp,min_pos;
int32_t min_idx;
int32_t i,j,idx;
uint32_t cell;
uint32_t old[81];
uint32_t unsolved_pieces = 0;
uint32_t *bptr, *nbptr;
 
int32_t stack_pos = 0;
int32_t stack_size = (1<<6);
uint32_t **stack = 0;
stack = (uint32_t**)malloc(sizeof(uint32_t*)*stack_size);
for(i=0;i<stack_size;i++)
{
stack[i] = (uint32_t*)malloc(sizeof(uint32_t)*81);
}
 
memcpy(stack[stack_pos++], board, sizeof(uint32_t)*81);
 
//printf("%d poss\n", count_poss(board));
while(stack_pos > 0)
{
itrs++;
unsolved_pieces = 0;
bptr = stack[--stack_pos];
bzero(os,sizeof(uint32_t)*81);
solve(bptr,os);
rc = check_correct(bptr, &unsolved_pieces);
/* solved puzzle */
if(rc == 1 && unsolved_pieces == 0)
{
memcpy(board, bptr, sizeof(uint32_t)*81);
goto solved_puzzle;
}
/* traversed to bottom of search tree and
* didn't find a valid solution */
if(rc == 0 && unsolved_pieces == 0)
{
continue;
}
find_min(bptr, &min_idx, &min_pos);
cell = bptr[min_idx];
while(cell != 0)
{
tmp = find_first_set(cell);
cell &= ~(1 << tmp);
nbptr = stack[stack_pos];
stack_pos++;
memcpy(nbptr, bptr, sizeof(uint32_t)*81);
nbptr[min_idx] = 1<<tmp;
assert(stack_pos < stack_size);
}
}
solved_puzzle:
for(i=0;i<stack_size;i++)
{
free(stack[i]);
}
free(stack);
 
return itrs;
}
/sudoku/branches/zynq/sw/Makefile
0,0 → 1,5
CXX := arm-linux-gnueabi-g++
CXXFLAGS := -static -O3
 
sudoku-search: main.cc driver.h counters.h counters.cc
$(CXX) $(CXXFLAGS) $^ -o $@

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.