Skip to content

Instantly share code, notes, and snippets.

@daxfohl
Last active September 21, 2020 07:36
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save daxfohl/2884473 to your computer and use it in GitHub Desktop.
Save daxfohl/2884473 to your computer and use it in GitHub Desktop.
verilog sudoku
module trigger(clk, rxReady, rxData, txBusy, txStart, txData);
input clk;
input[7:0] rxData;
input rxReady;
input txBusy;
output reg txStart;
output reg[7:0] txData;
integer countIO;
reg[8:0] data[0:8][0:8];
localparam read=0, solving=1, write1=2, write2=3;
localparam ROW=0, COL=1, SQ=2;
integer state;
initial begin
txStart <= 0;
state <= read;
end
always @(posedge clk) begin
integer ioCell, ioByte, ioCol, ioRow;
ioByte = countIO%4;
ioCell = countIO/4;
ioCol = ioCell%9;
ioRow = ioCell/9;
case (state)
read:
if (rxReady) begin
data[ioRow][ioCol][ioByte*8+7 -:8] <= rxData;
if (countIO == 81*4-1) begin
countIO <= 0;
state <= state + 1;
end else begin
countIO <= countIO + 1;
end
end
solving: begin
integer r,c,i,j,v,rgn,rgnType;
reg finished;
reg[8:0] mask[0:8][0:8];
reg[8:0] rowMask[0:8];
reg[8:0] colMask[0:8];
reg[8:0] sqMask[0:8];
reg[8:0] dataNew[0:8][0:8];
reg solved[0:8][0:8];
for (r=0; r<9; r=r+1) begin
for (c=0; c<9; c=c+1) begin
dataNew[r][c] = data[r][c];
end
end
for (rgnType=0; rgnType<3; rgnType=rgnType+1) begin
for (rgn=0; rgn<9; rgn=rgn+1) begin
reg[8:0] cells[0:8];
reg[8:0] exactlyOneCellContainsV;
for (i=0; i<9; i=i+1) begin
cells[i] = rgnType == ROW ? dataNew[rgn][i]
: rgnType == COL ? dataNew[i][rgn]
: dataNew[rgn/3*3+i%3][rgn%3*3+i/3];
end
for (v=0; v<9; v=v+1) begin
reg atLeastOneCellContainsV;
reg twoCellsContainV;
atLeastOneCellContainsV = 0;
twoCellsContainV = 0;
for (i=0; i<9; i=i+1) begin
twoCellsContainV = twoCellsContainV || atLeastOneCellContainsV && cells[i][v];
atLeastOneCellContainsV = atLeastOneCellContainsV || cells[i][v];
end
exactlyOneCellContainsV[v] = atLeastOneCellContainsV && !twoCellsContainV;
end
for (i=0; i<9; i=i+1) begin
reg[8:0] dataTest;
dataTest = exactlyOneCellContainsV & cells[i];
cells[i] = dataTest==0 ? cells[i] : dataTest;
end
for (i=0; i<9; i=i+1) begin
dataNew[rgnType == ROW ? rgn
: rgnType == COL ? i
: rgn/3*3+i%3]
[rgnType == ROW ? i
: rgnType == COL ? rgn
: rgn%3*3+i/3] = cells[i];
end
end
end
for (r=0; r<9; r=r+1) begin
for (c=0; c<9; c=c+1) begin
reg atLeastOne;
reg moreThanOne;
atLeastOne = 0;
moreThanOne = 0;
for (i=0; i<9; i=i+1) begin
moreThanOne = moreThanOne || atLeastOne && dataNew[r][c][i];
atLeastOne = atLeastOne || dataNew[r][c][i];
end
solved[r][c] = atLeastOne && !moreThanOne;
mask[r][c] = solved[r][c] ? ~dataNew[r][c] : ~0;
end
end
for (i=0; i<9; i=i+1) begin
rowMask[i] = ~0;
colMask[i] = ~0;
sqMask[i] = ~0;
for (j=0; j<9; j=j+1) begin
rowMask[i] = rowMask[i]&mask[i][j];
colMask[i] = colMask[i]&mask[j][i];
sqMask[i] = sqMask[i]&mask[i/3*3+j%3][i%3*3+j/3];
end
end
finished = 1;
for (r=0; r<9; r=r+1) begin
for (c=0; c<9; c=c+1) begin
reg[8:0] newVal;
newVal = solved[r][c] ? dataNew[r][c] : rowMask[r]&colMask[c]&sqMask[r/3*3+c/3];
finished = finished && newVal == data[r][c];
data[r][c] = newVal;
end
end
if (finished) begin
state <= write1;
end end
write1:
if (!txBusy) begin
txData <= data[ioRow][ioCol][ioByte*8+7 -:8];
txStart <= 1;
state <= write2;
end
write2: begin
txStart <= 0;
if (countIO != 81*4-1) begin
countIO <= countIO + 1;
state <= write1;
end else begin
countIO <= 0;
state <= read;
end end
endcase
end
endmodule
@sowmyakodem
Copy link

Can this be implemented on fpga?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment